C语言背包问题求最大总价值（c语言背包问题）

大家好，我是小新，我来为大家解答以上问题。C语言背包问题求最大总价值，c语言背包问题很多人还不知道，现在让我们一起来看看吧！

1、提问者的这程序中用了递归算法，不过逻辑上有个小bug，就是在判断到n==0时，如果还有容量，那么返回的应该是第一个物品的重量而不是0。你可以改变容量C或物品参数来检验算法的逻辑正确性。

2、       关于输出选择的物品，我加了一个数组，用来标记选择的物品。因为做完所有递归后只有最外层的标记是有效的，所以最后用了一个for循环来完成各层的标记。下面是改动后的程序：

3、　　

4、    int a[5]={0};

5、　　int MaxW(int n, int C, int *Volunme, int *Weight)

6、　　{

7、　　int W=0,W1=0,W2=0;

8、　　if (n == 0)

9、　　{

10、　　if(C >= Volunme[0])

11、　　{

12、　　a[0]=1;

13、　　return W=1;

14、　　}

15、　　else

16、　　return 0;

17、　　}

18、　　else if(C >= Volunme[n])//背包剩余空间可以放下物品n

19、　　{

20、　　W1 = MaxW(n-1, C-Volunme[n],Volunme,Weight) + Weight[n]; //放入n所能得到的重量

21、　　W2 = MaxW(n-1,C,Volunme,Weight); //不放n所能得到的重量

22、　　W=(W1>W2?W1:W2);

23、　　a[n]=(W1>W2?1:0);

24、　　}

25、　　else//背包空间放不下n,返回判断放n-1的情况

26、　　{

27、　　return MaxW(n-1,C,Volunme,Weight);

28、　　}

29、　　return W;

30、　　}

31、　　int main(void)

32、　　{

33、　　int n=5;int C=7;

34、　　int Volunme[] = {1,2,3,4,5};

35、　　int Weight[] = {1,2,5,7,8};

36、　　printf("最大重量为%d ",MaxW(n-1,C,Volunme,Weight));

37、　　for(int i=n-2;i>=0;i--)

38、　　{

39、　　a[i]=0;

40、　　if(a[i+1]==1)

41、　　{

42、　　C-=Volunme[i+1];

43、　　Weight[i+1]=0;

44、　　}

45、　　MaxW(i,C,Volunme,Weight);

46、　　}

47、　　printf("选择的物品号是：");

48、　　for(int i=0;i<5;i++)

49、　　{

50、　　if(a[i]==1)

51、　　printf("#%d  ",i+1);

52、　　}

53、　　printf(" ");

54、　　return 0;

55、　　}

本文到此讲解完毕了，希望对大家有帮助。