背包问题回溯法分别用回溯法和动态规划求0/1背包问题（C语言代码）

贪心算法 部分背包问题

[背包问题]有一个背包，背包容量是M=150。

有7个物品，物品可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 分析： 目标函数： ∑pi最大 约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150) （1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？ （2）每次挑选所占重量最小的物品装入是否能得到最优解？ （3）每次选取单位重量价值最大的物品，成为解本题的策略。

? 值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。

贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。

可惜的是，它需要证明后才能真正运用到题目的算法中。

一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下： （1）贪心策略：选取价值最大者。

反例： W=30 物品：A B C 重量：28 12 12 价值：30 20 20 根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。

（2）贪心策略：选取重量最小。

它的反例与第一种策略的反例差不多。

（3）贪心策略：选取单位重量价值最大的物品。

反例： W=30 物品：A B C 重量：28 20 10 价值：28 20 10 根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。

证明题：用解背包问题的贪心算法解0-1背包问题时不一定得到最优解 急求！！

贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最优解上加以考虑，它所作出的选择只是在某种意义上的局部最优解。

背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。

用贪心算法求解背包问题的步骤是，首先计算每种物品单位重量的价值vi/wi；然 后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。

若将这种物品全部装入背包后，背包内的物品总量未超过c，则选择单位重量价值次高的物 品并尽可能多地装入背包。

依此策略一直进行下去，直到背包装满为止。

在最后一步包装不下时可能会分割物品，而0-1背包问题不能分割物品，故不一定得到最优解。

取一反例即可说明

求解背包问题算法的设计与实现

这个不像是背包问题，这是求从一个集合内找个所有子集合，然后其和等于给定值的。

这个可以用回溯做. 如下面程序: #include<stdio.h> #define N 100 int weight[N];//物品重量 int n;//物品总数 int visit[N];//用了哪些物品，为了输出 int total;//需要的重量 void solve(int p,int data,int num) //p表示开始查找的坐标，data表示当前的重量 。

num表示找到的个数。

{ int i; //找到一个解 if(data==total) { for(i=0;i<num;i++) printf("%d ",visit[i]); printf(" "); return ; } for(i=p;i<n;i++) { if(weight[i]+data<=total) { visit[num]=weight[i]; solve(i+1,data+weight[i],num+1); } } } int main() { int i; scanf("%d",&n);//输入个数 for(i=0;i<n;i++) scanf("%d",&weight[i]);//输入值。

scanf("%d",&total);//要查找的数。

solve(0,0,0);//查找。

return 0; }

解决0-1背包问题需要排序的有哪些算法

用贪心算法求解0-1背包问题的步骤是，首先计算每种物品单位重量的价值vi/wi；然后，将物品的vi/wi的大小进行降序进行排列，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。

若将这种物品全部装入背包后，背包内的物品总量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包。

依此策略一直进行下去，直到背包装满为止。

分别用回溯法和动态规划求0/1背包问题（C语言代码）

#include <stdio.h> #include <malloc.h> #include <windows.h>typedef struct goods { double *value; //价值 double *weight; //重量 char *select; //是否选中到方案 int num;//物品数量 double limitw; //限制重量 }GOODS; double maxvalue,totalvalue;//方案最大价值,物品总价值 char *select1; //临时数组 void backpack(GOODS *g, int i, double tw, )//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值 { int k; if (tw + g->weight[i] <= g->limitw)//将物品i包含在当前方案,且重量小于等于限制重量 { select1[i] = 1; //选中第i个物品 if (i < g->num - 1) //若物品i不是最后一个物品 backpack(g, i + 1, tw + g->weight[i],); //递归调用,继续添加下一物品 else //若已到最后一个物品 { for (k = 0; k < g->num; ++k) //将状态标志复制到option数组中 g->select[k] = select1[k]; maxvalue =; //保存当前方案的最大价值 } } select1[i] = 0; //取消物品i的选择状态 if - g->value[i] > maxvalue)//若物品总价值减去物品i的价值还大于maxv方案中已有的价值,说明还可以继续向方案中添加物品 { if (i < g->num - 1) //若物品i不是最后一个物品 backpack(g, i + 1, tw, - g->value[i]); //递归调用,继续加入下一物品 else //若已到最后一个物品 { for (k = 0; k < g->num; ++k) //将状态标志复制到option数组中 g->select[k] = select1[k]; maxvalue = - g->value[i]; //保存当前方案的最大价值(从物品总价值中减去物品i的价值) } } } int main() { double sumweight; GOODS g; int i; printf("背包最大重量:"); scanf("%lf",&g.limitw); printf("可选物品数量:"); scanf("%d",&g.num); if(!(g.value = (double *)malloc(sizeof(double)*g.num)))//分配内存保存物品价值 { printf("内存分配失败 "); exit(0); } if(!(g.weight = (double *)malloc(sizeof(double)*g.num)))//分配内存保存物品的重量 { printf("内存分配失败 "); exit(0); } if(!(g.select = (char *)malloc(sizeof(char)*g.num)))//分配内存保存物品的重量 { printf("内存分配失败 "); exit(0); } if(!(select1 = (char *)malloc(sizeof(char)*g.num)))//分配内存保存物品的重量 { printf("内存分配失败 "); exit(0); } totalvalue=0; for (i = 0; i < g.num; i++) { printf("输入第%d号物品的重量和价值:",i + 1); scanf("%lf%lf",&g.weight[i],&g.value[i]); totalvalue+=g.value[i];//统计所有物品的价值总和 } printf(" 背包最大能装的重量为:%.2f ",g.limitw); for (i = 0; i < g.num; i++) printf("第%d号物品重:%.2f,价值:%.2f ", i + 1, g.weight[i], g.value[i]); for (i = 0; i < g.num; i++)//初始设各物品都没加入选择集 select1[i]=0; maxvalue=0;//加入方案物品的总价值 backpack(&g,0,0.0,totalvalue); //第0号物品加入方案,总重量为0,所有物品价值为totalvalue sumweight=0; printf(" 可将以下物品装入背包,使背包装的物品价值最大: "); for (i = 0; i < g.num; ++i) if (g.select[i]) { printf("第%d号物品,重量:%.2f,价值:%.2f ", i + 1, g.weight[i], g.value[i]); sumweight+=g.weight[i]; } printf(" 总重量为: %.2f,总价值为:%.2f ", sumweight, maxvalue ); // getch(); return 0; }