动态规划之-0-1背包问题及改进VIP免费

有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。在选择装入背包的物品时，对于每种物品i，只能选择装包或不装包，不能装入多次，也不能部分装入，因此成为0-1背包问题。形式化描述为：给定n个物品，背包容量C>0,重量第i件物品的重量w[i]>0,价值v[i]>0,1≤i≤n.要求找一n元向量(X1,X2,…,Xn,),Xi{0,1},∈使得∑（w[i]*Xi）≤C,且∑v[i]*Xi达最大.即一个特殊的整数规划问题。数学描述为：求解最优值：设最优值m(i,j)为背包容量为j、可选择物品为i，i+1，……，n时的最优值(装入包的最大价值)。所以原问题的解为m(1，C)将原问题分解为其子结构来求解。要求原问题的解m(1，C)，可从m(n，C)，m(n-1，C)，m(n-2，C).....来依次求解，即可装包物品分别为（物品n）、（物品n-1，n）、（物品n-2，n-1，n）、……、（物品1，物品2，……物品n-1，物品n）。最后求出的值即为最优值m(1，C)。若求m(i,j)，此时已经求出m(i+1,j)，即第i+1个物品放入和不放入时这二者的最大值。对于此时背包剩余容量j=0,1,2,3……C，分两种情况：(1)当w[i]>j，即第i个物品重量大于背包容量j时，m(i,j)=m(i+1,j)(2)当w[i]<=j，即第i个物品重量不大于背包容量j时，这时要判断物品i放入和不放入对m的影响。若不放入物品i，则此时m(i,j)=m(i+1,j)若放入物品i，此时背包剩余容量为j-w[i]，在子结构中已求出当容量k=0,1,2……C时的最优值m(i+1,k)。所以此时m(i,j)=m(i+1,j-w[i])+v[i]。取上述二者的最大值，即m(i,j)=max{m(i+1,j)，m(i+1,j-w[i])+v[i]}总结得出状态转移方程为：该算法的python代码实现：1#0-1背包问题2__author__='ice'345#背包容量0~capacity,不是0~capacity-16defknapsack(weight,value,capacity):7iflen(weight)!=len(value):8print("parametererr!")9return10obj_num=len(weight)11result=[[]forxinrange(obj_num)]12divide=min(weight[-1],capacity)13result[-1]=[0forxinrange(divide)]14result[-1].extend(value[-1]forxinrange(divide,capacity+1))15foriinreversed(list(range(1,obj_num-1))):16divide=min(weight[i],capacity)17forjinrange(divide):18result[i].append(result[i+1][j])19forjinrange(divide,capacity+1):20result[i].append(max(result[i+1][j],result[i+1][j-weight[i]]+value[i]))2122result[0]={capacity:result[1][capacity]}23ifweight[0]<=capacity:24result[0][capacity]=max(result[1][capacity],result[1][capacity-weight[0]]+value[0])2526vector=[0forxinrange(obj_num)]27capacity_temp=capacity28foriinrange(obj_num-1):29ifresult[i][capacity_temp]!=result[i+1][capacity_temp]:30vector[i]=131capacity_temp-=weight[i]3233ifcapacity_temp==0:34vector[-1]=035else:36vector[-1]=13738return{'total_value':result[0][capacity],'select':vector}但是,该算法有两个明显的缺点：1，基于上述代码，因为数组索引的需要，要求所给物品重量为整数。2，当背包容量C很大时，算法所需计算时间较多。当C>2^n时，需要Ω(n*2^n)计算时间。所以,改进算法如下：对于函数m(i,j)的值，当i确定，j为自变量时，是单调不减的跳跃式增长，如图所示。而这些跳跃点取决于在（物品i，物品i+1，……物品n）中选择放入哪些物品使得在放入重量小于容量j(0<=j<=C)的情况下m取得最大值。对于每一个确定的i值，都有一个对应的跳跃点集Pi={(j,m(i,j))，……}。j始终小于等于C(1)开始求解时，先求Pi，初始时Pn+1={(0，0)}，i=n+1，由此按下列步骤计算Pi-1，Pi-2……P1，即Pn，Pn-1，……P1(2)求Qi，利用Pi求出m（i，j-w[i-1]）+v[i-1]，即Pi当放入物品i-1后的变化后的跳跃点集Qi={(j+w[i-1],m(i,j)+v[i-1])，……}，在函数图像上表现为所有跳跃点横轴坐标右移w[i-1]，纵轴坐标上移v[i-1]。(3)求Pi-1，即求PiQ∪i然后再去掉受控跳跃点后的点集。此处有个受控跳跃点的概念：若点(a,b)，(c,d)PiQi∈∪，且a<=c，b>d，则(c,d)受控于(a,b)，所以(c,d)∉Pi-1。去掉受控跳跃点，是为了求得...