网站短期电脑培训班学费,类似wordpress的程序,重庆相亲网,互联网推广销售好做吗转载自#xff1a;https://blog.csdn.net/qian2213762498/article/details/79420269
【回溯法】#xff0d;#xff0d;01背包问题
1、问题描述 给定n种物品和一背包。物品i的重量是wi0#xff0c;其价值为vi0#xff0c;背包的容量为c。问应如何选择装入背包中…转载自https://blog.csdn.net/qian2213762498/article/details/79420269
【回溯法】01背包问题
1、问题描述 给定n种物品和一背包。物品i的重量是wi0其价值为vi0背包的容量为c。问应如何选择装入背包中的物品使得装入背包中物品的总价值最大 要求使用回溯法 例如 、算法分析
【整体思路】 01背包属于找最优解问题用回溯法需要构造解的子集树。对于每一个物品i对于该物品只有选与不选2个决策总共有n个物品可以顺序依次考虑每个物品这样就形成了一棵解空间树 基本思想就是遍历这棵树以枚举所有情况最后进行判断如果重量不超过背包容量且价值最大的话该方案就是最后的答案。 在搜索状态空间树时只要左子节点是可一个可行结点搜索就进入其左子树。对于右子树时先计算上界函数以判断是否将其减去剪枝。 上界函数bound():当前价值cw剩余容量可容纳的最大价值当前最优价值bestp。 为了更好地计算和运用上界函数剪枝选择先将物品按照其单位重量价值从大到小排序此后就按照顺序考虑各个物品。
【举例说明】 对于n4的0/1背包问题其解空间树如图所示树中的16个叶子结点分别代表该问题的16个可能解。
【算法设计】 利用回溯法试设计一个算法求出0-1背包问题的解也就是求出一个解向量i 即对n个物品放或不放的一种的方案 其中 (i 0 或i 0表示物体不放入背包i 1表示把物体放入背包。
在递归函数Backtrack中 当in时算法搜索至叶子结点得到一个新的物品装包方案。此时算法适时更新当前的最优价值 当in时当前扩展结点位于排列树的第i-1层此时算法选择下一个要安排的物品以深度优先方式递归的对相应的子树进行搜索对不满足上界约束的结点则剪去相应的子树。
【时间复杂度优化】 因为物品只有选与不选2个决策而总共有n个物品所以时间复杂度为。 因为递归栈最多达到n层而且存储所有物品的信息也只需要常数个一维数组所以最终的空间复杂度为O(n)。
相关链接
相关链接
相关链接
【源代码】
#include iostream
#include stdio.h
//#include conio.h
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(i1;in;i)perp[i]v[i]/w[i]; //计算单位价值单位重量的物品价值for(i1;in-1;i){for(ji1;jn;j)if(perp[i]perp[j])//冒泡排序perp[],order[],sortv[],sortw[]{temp perp[i]; //冒泡对perp[]排序perp[i]perp[i];perp[j]temp;temporderorder[i];//冒泡对order[]排序order[i]order[j];order[j]temporder;temp v[i];//冒泡对v[]排序v[i]v[j];v[j]temp;tempw[i];//冒泡对w[]排序w[i]w[j];w[j]temp;}}
}//回溯函数
void backtrack(int i)
{ //i用来指示到达的层数第几步从0开始同时也指示当前选择玩了几个物品double bound(int i);if(in) //递归结束的判定条件{bestp cp;return;}//如若左子节点可行则直接搜索左子树;//对于右子树先计算上界函数以判断是否将其减去if(cww[i]c)//将物品i放入背包,搜索左子树{cww[i];//同步更新当前背包的重量cpv[i];//同步更新当前背包的总价值put[i]1;backtrack(i1);//深度搜索进入下一层cw-w[i];//回溯复原cp-v[i];//回溯复原}if(bound(i1)bestp)//如若符合条件则搜索右子树backtrack(i1);
}//计算上界函数功能为剪枝
double bound(int i)
{ //判断当前背包的总价值cp剩余容量可容纳的最大价值当前最优价值double leftw c-cw;//剩余背包容量double b cp;//记录当前背包的总价值cp,最后求上界//以物品单位重量价值递减次序装入物品while(in w[i]leftw){leftw-w[i];bv[i];i;}//装满背包if(in)bv[i]/w[i]*leftw;return b;//返回计算出的上界}int main()
{int i;printf(请输入物品的数量和背包的容量);scanf(%d %lf,n,c);/*printf(请输入物品的重量和价值\n);for(i1;in;i){printf(第%d个物品的重量,i);scanf(%lf,w[i]);printf(第%d个物品的价值是,i);scanf(%lf,v[i]);order[i]i;}*/printf(请依次输入%d个物品的重量:\n,n);for(i1;in;i){scanf(%lf,w[i]);order[i]i;}printf(请依次输入%d个物品的价值:\n,n);for(i1;in;i){scanf(%lf,v[i]);}knapsack();backtrack(1);printf(最优价值为%lf\n,bestp);printf(需要装入的物品编号是);for(i1;in;i){if(put[i]1)printf(%d ,order[i]);}return 0;
}
