解决01背包问题算法比较.ppt

The compare of the algorithms for solving 0/1 knapsack problems,解决0/1背包问题算法比较,0/1背包问题概述,在0/1背包问题中，需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品 i的重量为wi,价值为pi。对于可行的背包装载，背包中的物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即 取得最大值。约束条件为 c和。在这个表达式中，需求出xi的值。xi=1表示物品i装入背包中，xi=0表示物品i不装入背包。,动态规划求解0-1背包问题,动态规划原理：动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。,动态规划求解0-1背包问题,在0/1背包问题中需要决定x1xn的值。假设按i=1，2，,n的次序来确定xi的值。如果置x1=0，则问题转变为相对于其余物品，背包容量仍为c的背包问题。若置x1=1，问题就变为关于最大背包容量为 c-w1的问题。现设r c，c-w1为剩余的背包容量。,动态规划求解0-1背包问题,在第一次决策之后，剩下的问题便是考虑背包容量为r时的决策。不管x1是0或者1，x2，xn必须第一次决策之后的一个最优方案，如果不是，则会有一个更好的方案y2，yn，因而x1，y2，yn是一个更好的方案。,动态规划求解0-1背包问题,最优决策序列由最优决策子序列组成。假设f（i，y）表示剩余容量y，剩余物品为i，i+1，n时的最优解的值，即：pn y=wn f（n，y）=0 0=wi f（i，y）=f(i+1,y)0=ywi,动态规划求解0-1背包问题,利用最优序列由最优子序列构成的结论，可得到f的递归式。f（1，c）是初始时背包问题的最优解。可使用一式通过递归或迭代来求解f（1，c）。从f（n，*）开始迭式，f（n，*）由一式得出，然后由二式递归计算f（1，*）（i=n-1,n-2,2）,最后由二式得出f（1，c）。,贪婪算法解决0/1背包问题,从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。,贪婪算法解决0/1背包问题,另一种方案是重量贪婪策略：从剩下的物品中选择可以装入背包的重量最小的物品。在一般情况下不一定能得到最优解。,贪婪算法解决0/1背包问题,还可以利用另一方案，价值密度pi/wi贪婪算法，这种选择准则为：从剩余物品种选择可以装入包的价值密度最大的物品，这种策略也不能保证得到最优解。,贪婪算法解决0/1背包问题,可以建立贪婪启发式方法来提供解，使解的结果与最优解的值之差在最优解的x%（x100）之内。首先将最多k件物品放入背包，如果这k件物品重量大于c，则放弃它。否则剩余的容量用来考虑将剩余物品按价值密度pi/wi递减的顺序装入。通过考虑由启发法产生的解法种最多为k件物品的所有可能的子集来得到最优解。,贪婪算法解决0/1背包问题,这种修改后的贪婪启发法称为k阶优化方法（k-optimal）。也就是，若从答案中取出k件物品，并放入另外k件，获得结果在最佳值的50%以内；当k=2时，则在33.33%以内等等，这种启发式方法的执行时间随k的增大而增加，需要测试的子集数目为O（），每一个子集所需时间为O（n），因此当k0时总的时间开销为O()。,贪婪算法解决0/1背包问题,600种随机测试的统计结果,回溯法解决0/1背包问题,回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。,回溯法解决0/1背包问题,三个对象的背包问题的解空间 1 0 1 0 1 0 1 0 1 0 1 0 1 0,A,B,K,G,I,F,H,E,J,N,M,L,D,C,Q,回溯法解决0/1背包问题,运用回溯法解题通常包含以下三个步骤：a.针对所给问题，定义问题的解空间；b.确定易于搜索的解空间结构；c.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；,回溯法解决0/1背包问题,考察如下背包问题：n=3，w=20，15，15，p=40，25，25且c=30.,回溯法解决0/1背包问题,#includeusing namespace std;class Knapfriend int Knapsack(int p,int w,int c,int n);public:void print()for(int m=1;m=n;m+)coutbestxm;coutendl;private:int Bound(int i);void Backtrack(int i);int c;/背包容量 int n;/物品数 int*w;/物品重量数组 int*p;/物品价值数组 int cw;/当前重量 int cp;/当前价值 int bestp;/当前最优值 int*bestx;/当前最优解 int*x;/当前解;,回溯法解决0/1背包问题,int Knap:Bound(int i)/计算上界int cleft=c-cw;/剩余容量int b=cp;/以物品单位重量价值递减序装入物品while(i=n,回溯法解决0/1背包问题,void Knap:Backtrack(int i)if(in)if(bestpbestp)/搜索右子树 xi=0;Backtrack(i+1);,回溯法解决0/1背包问题,class Objectfriend int Knapsack(int p,int w,int c,int n);public:int operator=a.d);private:int ID;float d;,回溯法解决0/1背包问题,int Knapsack(int p,int w,int c,int n)/为Knap:Backtrack初始化int W=0;int P=0;int i=1;Object*Q=new Objectn;for(i=1;i=n;i+)Qi-1.ID=i;Qi-1.d=1.0*pi/wi;P+=pi;W+=wi;if(W=c)return P;/装入所有物品/依物品单位重量排序float f;for(i=0;in;i+)for(int j=i;jn;j+)if(Qi.dQj.d)f=Qi.d;Qi.d=Qj.d;Qj.d=f;,回溯法解决0/1背包问题,Knap K;K.p=new intn+1;K.w=new intn+1;K.x=new intn+1;K.bestx=new intn+1;K.x0=0;K.bestx0=0;for(i=1;i=n;i+)K.pi=pQi-1.ID;K.wi=wQi-1.ID;K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;/回溯搜索K.Backtrack(1);K.print();delete Q;delete K.w;delete K.p;return K.bestp;,分枝定界法解决0/1背包问题,分枝限界法的基本思想 1.分枝限界法与回溯法的不同（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分枝限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分枝限界法则以广度优先或以最小耗费优先的方式搜索解空间树,分枝定界法解决0/1背包问题,2.分枝限界法基本思想 分枝限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分枝限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,分枝定界法解决0/1背包问题,3.常见的两种分枝限界法（1）队列式(FIFO)分枝限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分枝限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。,分枝定界法解决0/1背包问题,0-1背包问题算法的思想 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值,分枝定界法解决0/1背包问题,下面比较分别利用FIFO分枝定界和最大收益分枝定界方法来解决如下背包问题：n=3，w=20，15，15，p=40，25，25，c=30,分枝定界法解决0/1背包问题,上界函数while(i=n/b为上界函数,分枝定界法解决0/1背包问题,while(i!=n+1)/非叶结点 double wt=cw+wi;if(wt bestp)bestp=cp+pi;addLiveNode(up,cp+pi,cw+wi,i+1,enode,true);up=bound(i+1);if(up=bestp)/检查右儿子节点 addLiveNode(up,cp,cw,i+1,enode,false);/取下一个扩展节点（略）,