动态规划法求01背包问题[c语言实现]

算法设计与分析期末考试题&＃xff1a;

请编程实现0-1背包问题的回溯求解方法&＃xff0c;0-1背包即一个物品要么选&＃xff0c;要么不选&＃xff0c;在不超过背包容量的前提下&＃xff0c;使得背包的价值量最大&＃xff0c;要求编写主程序调用该算法实现下列问题的求解

n &＃61; 6&＃xff0c;c &＃61; 20  v &＃61;&＃xff08;4,8,15,1,6,3&＃xff09;&＃xff0c;W &＃61;&＃xff08;5,3,2,10,4,8&＃xff09;

其中n为物品个数&＃xff0c;c为背包载重量&＃xff0c;v表示物品的价值&＃xff0c;W表示物品的重量。请问对于此0-1背包问题&＃xff0c;应该如何选择放进去的物品才能使背包的物品总价值最大&＃xff0c;能获得的总价值多少&＃xff1f;

#include
int n,c,bestp;//物品的个数&＃xff0c;背包的容量&＃xff0c;最大价值
int p[10000],w[10000],x[10000],bestx[10000];//物品的价值&＃xff0c;物品的重量&＃xff0c;x[i]暂存物品的选中情况,物品的选中情况void Backtrack(int i,int cp,int cw)
{ //cw当前包内物品重量&＃xff0c;cp当前包内物品价值int j;if(i>n)//回溯结束{if(cp>bestp){bestp&＃61;cp;for(i&＃61;0;i<&＃61;n;i&＃43;&＃43;) bestx[i]&＃61;x[i];}}else for(j&＃61;0;j<&＃61;1;j&＃43;&＃43;) {x[i]&＃61;j;if(cw&＃43;x[i]*w[i]<&＃61;c) {cw&＃43;&＃61;w[i]*x[i];cp&＃43;&＃61;p[i]*x[i];Backtrack(i&＃43;1,cp,cw);cw-&＃61;w[i]*x[i];cp-&＃61;p[i]*x[i];}}
}int main()
{int i;bestp&＃61;0; printf("请输入背包最大容量:\n");scanf("%d",&c);printf("请输入物品个数:\n");scanf("%d",&n);printf("请依次输入物品的重量:\n");for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;) scanf("%d",&w[i]);printf("请依次输入物品的价值:\n");for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;) scanf("%d",&p[i]);Backtrack(1,0,0);printf("最大价值为:\n");printf("%d\n",bestp);printf("被选中的物品依次是(0表示未选中&＃xff0c;1表示选中)\n");for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;) printf("%d ",bestx[i]);printf("\n");return 0;
}