0 1背包问题的多种解法.docx

0_1背包问题的多种解法、问题描述0/1背包问题:现有n种物品,对1<=i<=n,已知第i种物品的重量为正整数W,价值为正整数V,背包能承受的最大载重量为正整数V,现要求找出这n种物品的一个子集,使得子集中物品的总重量不超过W且总价值尽量大。(注意:这里对每种物品或者全取或者一点都不取,不允许只取一部分)、算法分析根据问题描述,可以将其转化为如下的约束条件和目标函数:nwixiWii ⑴Xi{0,1(1in)nmaxvix(2)i1于是,问题就归结为寻找一个满足约束条件( 1),并使目标函数式(2)达到最大的解向量(X1,X2,X3,……Xn)。首先说明一下0-1背包问题拥有最优解假设(X1,X2,X3,……,Xn)是所给的问题的一个最优解,则(X2,X3,……,Xn)是下面问题的一个最优解:nWi2Xi {0,1}(2W1X1maxin) invix。如果不是的话,设(y2>y3>....2..,yn)是这个问题的一个最优解,则n nViyi ViXii2 i2,且W1X1n nWiyi W。因此,V1X1 Viyii2 i2n nv1x1 VjX VXi,这说明i2 i1(X1,y2,y3, ,yn)是所给的0-1背包问题比(X1,X2,X3, ,Xn)更优的解,从而与假设矛盾穷举法:用穷举法解决0-1背包问题,需要考虑给定n个物品集合的所有子集,找出所有可能的子集(总重量不超过背包重量的子集),计算每个子集的总重量,然后在他们中找到价值最大的子集。 由于精品程序过于简单,在这里就不再给出,用实例说明求解过程 。下面给出了4个物品和一个容量为10的背包,下图就是用穷举法求解0-1背包问题的过程。(a)四个物品和一个容量为10的背包序号子集总重量总价值序号子集总重量总价值1空集009{2,3}7522{1}74210{2,4}8373{2}31211{3,4}9654⑶44012{1,2,3}14不可行5{4}52513{1,2,4}15不可行6{1,2}105414{1,3,4}16不可行7{1,3}11不可行15{2,3,4}12不可行8{1,4}12不可行16{123,4}19不可行(b)用回溯法求解0-1背包问题的过程递归法:在利用递归法解决0-1背包问题时,我们可以先从第n个物品看起。每次的递归调用都会判断两种情况:背包可以放下第n个物品,则x[n]=1,并继续递归调用物品重量为W-w[n],物品数目为n-1的递归函数,并返回此递归函数值与 v[n]的和作为背包问题的最优解;背包放不下第n个物品,则x[n]=0,并继续递归调用背包容量为W物品数目为n-1的递归函数,并返回此递归函数值最为背包问题的最优解。-1背包问题的最优解。用递归法解0-1背包问题可以归结为下函数:KnapSack(n1,m) 没有选择物品nKnapSack(n,m)KnapSack(n1,mWn])v[n] 选择了物品n第一个式子表示选择物品n后得到价值KnapSack(n1,mw[n])v[n]比不选择物品n情况下得到的价值KnapSack(n1,m)小,所以最终还是不选择物品n;第二个式子刚好相反,选择物品n后的价值KnapSack(n1,mw[n])v[n]不小于不选择物品n情况下得到了价值KnapSack(n1,m),所以最终选择物品n。在递归调用的过程中可以顺便求出所选择的物品。 下面是标记物品被选情况的数组x[n]求解的具体函数表示:0 KnapSack(n,m)KnapSack(n1,m)x[n]1 KnapSack(n,m)KnapSack(n1,mw[n])v[n]在函数中,递归调用的主体函数为KnapSacKm表示背包的容量,n表示物品的数量,x[n]表示是否选择了第n个物品(1—选,0—不选)。每个物品的重量和价值信息分别存放在数组w[n]和v[n]中。具体的代码见《递归法》文件夹。贪心法:0-1背包问题与背包问题类似,所不同的是在选择物品i(1in)装入背包时,可以选择一部分,而不一定要全部装入背包。这两类问题都具有最优子结构性质,相当相似。但是背包问题可以用贪心法求解,而0-1背包问题却不能用贪心法求解。贪心法之所以得不到最优解,是由于物品不允许分割,因此,无法保证最终能将背包装满,部分闲置的背包容量使背包单位重量的价值降低了。事实上,在考虑0-1背包问题时,应比较选择物品和不选择物品所导致的方案,然后做出最优解。由此导出了许多相互重叠的子问题,所以,0-1背包问题可以用动态规划法得到最优解。在这里就不再用贪心法解0-1背包问题了。动态规划法分析:0-1背包问题可以看作是寻找一个序列(X1,X2,X3, ,Xn),对任一个变量Xi的判断是决定Xi=1精品还是Xi=