0-1背包问题-回溯法.pdf

《0-1背包问题-回溯法.pdf》由会员分享，可在线阅读，更多相关《0-1背包问题-回溯法.pdf（6页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、0-1背包问题-回溯法问题描述给定n种物品和个背包。物品i的重量是wi，其价值为vi，背包的容量为c。应如何选择装背包的物品，使得装背包中物品的总价值最?在选择装背包的物品时，对每种物品i只有2种选择，即装背包或不装背包。不能将物品i装背包多次，也不能只装部分的物品i。算法描述0-1背包问题是集选取问题。般情况下，0-1背包问题是NP难得。0-1背包问题的解空间可集树 表。在搜索解空间的时，只要其左节点是个可节点，搜索就进去其左树(约束条件)。当右树中可能包含最优解时才进右树搜索(限界函数)。否则就将右树剪去。计算右树中解的上界的更好法是将剩余物品依其单位重量价值排序，然后依次装物品，直装不下

2、时，再装物品的部分装满背包。由此得到的价值是右树中解的上界。为了便于计算上界，可先将物品按照单位重量价值由到排序，此后，只要按照顺序考察各个物品即可。在实现时，由Bound计算当前结点处的上界。在解空间树的当前扩展结点处，仅当要进右树时才计算右树的上界Bound，以判断是否将右树剪去。进左树时不需要计算上界，因为其上界与其节点上界相同。计算步骤1.计算每种物品单位重量的价值si=pi/wi2.依贪选择策略，将尽可能多的单位重量价值最的物品装背包。3.若将这种物品全部装背包后，背包内的物品总重量未超过C，则选择单位重量价值次的物品并尽可能多地装背包。4.依此策略直地进下去，直到背包装满为。例问题

3、描述假设有4个物品，物品的价值分别为p=9,10,7,4,重量分别为w=3,5,2,1,背包容量C=9，使回溯法求解此0-1背包问题，计算其最优值及最优解。要求画出求得最优解的解空间树,给出具体求解过程。要求中间被剪掉的结点标记。求解步骤按照单位重量价值由到排好序，按照顺序考查是否装物品物品单位重量价值：p1/w1,p2/w2,p3/w3,p4/w4=(3,2,3.5,4)按照物品单位重量价值由到排序：物品1234重量(w)1235价值(v)47910价值/重量(v/w)43.532上界计算 先装物品1，然后装物品2 和 3。装这三个物品后，剩余的背包容量为3，只能装物品4的3/5(2*3/5

4、=1)。即上界为4+7+9+2*(9-6)=26深度优先搜索解空间树，若左是可节点，才搜索进左树，否则将左树剪掉；若右树包含最优解，才搜索右树，否则将右树剪掉。以第个up=26为例，26=4+7+9+2*(9-6)打x的部分因为up值已经于等于Bestp了，所以没必要继续递归了。样例分析演算法#include using namespace std;class Objectpublic:int p;/价值 int w;/重量 int id;/物品的id;/物品数量 背包容量 当前价值 当前重量 最优值 总重量 总价值int n,c,cp,cw,bestp,total_w,total_p;int

5、 x100,best_x100;/记录暂时选取状态 记录最优选取状态Object O100;/存储物品的数组void Input()coutnc;cout请输每个物品的价值和重量：endl;for(int i=1;i Oi.pOi.w;Oi.id=i;bool cmp(const Object&a,const Object&b)return a.p/a.w b.p/b.w;void Initilize()cp=cw=total_w=total_p=bestp=0;for(int i=1;i=n;+i)total_p+=Oi.p;total_w+=Oi.w;/依照物品单位重量价值排序 sort(

6、O+1,O+n+1,cmp);/for(int i=1;i=n;+i)/cout Oi.id endl;/计算up值int Bound(int i)int temp_cw=c-cw;int temp_cp=cp;while(i=Oi.w)temp_cw-=Oi.w;temp_cp+=Oi.p;+i;/装满背包 if(i n)bestp=cp;for(int i=1;i=n;+i)best_xi=xi;return;if(cw+Oi.w bestp)xOi.id=0;Backtrack(i+1);void OutPut()coutbestp=bestpendl;cout选取的物品为:;for(int i=1;i=n;+i)if(best_xi=1)cout i ;int main()Input();Initilize();Backtrack(1);OutPut();测试例输请输物品个数和背包容量：4 9请输每个物品的价值和重量：9 310 57 24 1输出bestp=23选取的物品为:1 2 4因为输的数据是没有进排序的，所以和例中选取的1,3,4不同。但仅仅是顺序不同，其实是样的。将上的例排好序在进测试输请输物品个数和背包容量：4 9请输每个物品的价值和重量：4 17 29 310 5输出bestp=23选取的物品为:1 3 4