【回溯法】－－01背包问题
1、问题描述
给定n种物品和一背包。物品i的重量是wi>0，其价值为vi>0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？ （要求使用回溯法）
例如：
２、算法分析
【整体思路】
01背包属于找最优解问题，用回溯法需要构造解的子集树。对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树： 基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。
在搜索状态空间树时，只要左子节点是可一个可行结点，搜索就进入其左子树。对于右子树时，先计算上界函数，以判断是否将其减去（剪枝）。
上界函数bound():当前价值cw+剩余容量可容纳的最大价值<=当前最优价值bestp。
为了更好地计算和运用上界函数剪枝，选择先将物品按照其单位重量价值从大到小排序，此后就按照顺序考虑各个物品。
【举例说明】
对于n=4的0/1背包问题，其解空间树如图所示，树中的16个叶子结点分别代表该问题的16个可能解。
【算法设计】
利用回溯法试设计一个算法求出0-1背包问题的解，也就是求出一个解向量ｘi （即对n个物品放或不放的一种的方案）
其中， (ｘi = 0 或１，ｘi = 0表示物体ｉ不放入背包，ｘi ＝1表示把物体ｉ放入背包）。
【时间复杂度&&优化】
因为物品只有选与不选2个决策，而总共有n个物品，所以时间复杂度为
。
因为递归栈最多达到n层，而且存储所有物品的信息也只需要常数个一维数组，所以最终的空间复杂度为O(n)。
相关链接１
相关链接２
相关链接３
【源代码】
#include
#include
//#include
using namespace std; int n;//物品数量 double c;//背包容量 double v[100];//各个物品的价值 value double w[100];//各个物品的重量 weight double cw = 0.0;//当前背包重量 current weight double cp = 0.0;//当前背包中物品总价值 current value double bestp = 0.0;//当前最优价值best price double perp[100];//单位物品价值(排序后) per price int order[100];//物品编号 int put[100];//设置是否装入，为1的时候表示选择该组数据装入，为0的表示不选择该组数据 //按单位价值排序 void knapsack() { int i,j; int temporder = 0; double temp = 0.0; for(i=1;i<=n;i++) perp[i]=v[i]/w[i]; //计算单位价值（单位重量的物品价值） for(i=1;i<=n-1;i++) { for(j=i+1;j<=n;j++) if(perp[i]
n) //递归结束的判定条件 { bestp = cp; return; } //如若左子节点可行，则直接搜索左子树; //对于右子树，先计算上界函数，以判断是否将其减去 if(cw+w[i]<=c)//将物品i放入背包,搜索左子树 { cw+=w[i];//同步更新当前背包的重量 cp+=v[i];//同步更新当前背包的总价值 put[i]=1; backtrack(i+1);//深度搜索进入下一层 cw-=w[i];//回溯复原 cp-=v[i];//回溯复原 } if(bound(i+1)>bestp)//如若符合条件则搜索右子树 backtrack(i+1); } //计算上界函数，功能为剪枝 double bound(int i) { //判断当前背包的总价值cp＋剩余容量可容纳的最大价值<=当前最优价值 double leftw= c-cw;//剩余背包容量 double b = cp;//记录当前背包的总价值cp,最后求上界 //以物品单位重量价值递减次序装入物品 while(i<=n && w[i]<=leftw) { leftw-=w[i]; b+=v[i]; i++; } //装满背包 if(i<=n) b+=v[i]/w[i]*leftw; return b;//返回计算出的上界 } int main() { int i; printf("请输入物品的数量和背包的容量："); scanf("%d %lf",&n,&c); /*printf("请输入物品的重量和价值：\n"); for(i=1;i<=n;i++) { printf("第%d个物品的重量：",i); scanf("%lf",&w[i]); printf("第%d个物品的价值是：",i); scanf("%lf",&v[i]); order[i]=i; }*/ printf("请依次输入%d个物品的重量:\n",n); for(i=1;i<=n;i++){ scanf("%lf",&w[i]); order[i]=i; } printf("请依次输入%d个物品的价值:\n",n); for(i=1;i<=n;i++){ scanf("%lf",&v[i]); } knapsack(); backtrack(1); printf("最优价值为：%lf\n",bestp); printf("需要装入的物品编号是："); for(i=1;i<=n;i++) { if(put[i]==1) printf("%d ",order[i]); } return 0; }
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/176449.html原文链接：https://javaforall.net
