资源描述：
《动态规划之-0-1背包问题及改进.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、有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达最大.即一个特殊的整数规划问题。 数
2、学描述为： 求解最优值：设最优值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)，此时
3、已经求出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(
4、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!")9re
5、turn10obj_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)17forjin
6、range(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],r
7、esult[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
8、[-1]=13738return{'total_value':result[0][capacity],'select':vector}但是,该算法有两个明显的缺点：1，基于上述代码，因为数组索引的需要，要求所给物品重量为整数。2，当背
