资源描述：
《noi导刊 资源背包动态规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、背包类动态规划问题长沙市雅礼中学朱全民经典的背包问题（01背包）有N件物品;第i件物品Wi公斤;第i件物品价值Ci元;现有一辆载重M公斤的卡车;问选取装载哪些物品，使得卡车运送的总价值最大？搜索法对于每种物品，要么装上卡车，要么不装，因此，N种物品的装箱方案共有2N种。按每种物品进行搜索，方法如下：对第i种物品进行搜索如果所有的物品都搜索完，则更新最优解如果当前的估计达不到最优解，则回溯如果第i种物品能放，则放，并标记，否则选下一个物品清除标记回溯动态规划可以按每个物品进行规划，同样每种物品有选和不选两种选择设F(i,
2、j)表示前i件物品载重为j的最大效益，则有1<=i<=N,0<=j<=N初值：F(0,j)=0F(N,M)即答案显然时间复杂度为O(NM)主程序如下fori:=1tomdof[0,i]:=0;//初始化fori:=1tondof[i,0]:=0;fori:=1tondo//动态规划，递推求fforj:=1tomdobeginifj>=w[i]then//背包容量够大f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])else//背包容量不足f[i,j]:=f[i-1,j];end;满背包问题
3、（01背包）有N件物品;第i件物品Wi公斤;第i件物品价值Ci元;现有一辆载重M公斤的卡车;问选取装载哪些物品，使得卡车开车正好装满时，运送的总价值最大？若无法装满卡车，则输出无解。动态规划设F(i,j)表示前i件物品背包为j的最大效益，则有1<=i<=N,0<=j<=N初值：F(0,j)=0，F(1,j)=-∞F(N,M)即答案显然时间复杂度为O(NM)带条件的背包问题（1）有N件物品;第i件物品Wi公斤;第i件物品价值Ci元;第i件物品可能带0~2个附件；若装载附件，必须装载主件，反之没有约束；现有一辆载重M公斤的
4、卡车;问选取装载哪些物品，使得卡车运送的总价值最大？分析假设只有主件的情况，显然与经典背包问题完全相同！现在每个物品有附件，我们可以分成4种方案仅装载主件装载主件+第1个附件装载主件+第2个附件装载主件+2个附件由于上述4种并列，这是几种不同的决策同时规划即可动态规划设F(i,j)表示前i件物品背包为j的最优解，则有，1<=i<=N,0<=j<=M时间复杂度O(NM)多层背包问题有N件物品;第i件物品Wi公斤;第i件物品价值Ci元;现有一辆载重M公斤的卡车;第i件物品限制最多只能取Xi个；问选取装载哪些物品，使得卡车运
5、送的总价值最大？分析我们可以类似01背包问题，将第i种物品拆分成x[i]个，这样每个物品只有1件了,如下图:然后对所有的物品采用动态规划即可。F(i,j)=max{f(i-1,j-k*w[i])+k*c[i]}0<=k*w[i]<=j完全背包问题有N件物品;第i件物品Wi公斤;第i件物品价值Ci元;现有一辆载重M公斤的卡车;每次可以选取某种物品的任意多件装载；问选取装载哪些物品，使得卡车运送的总价值最大？分析类似多层背包问题将每个物品展开成X[i]=m/w[i]个，然后对所有的物品采用动态规划即可。若两件物品i、j满足
6、c[i]<=c[j]且w[i]>=w[j],则将物品i去掉,不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高的j换成物美价廉的i,得到至少不会更差的方案。由于每种物品有选和不选两种情况，可以将每种物品的2k个当成一个整体考虑。这样对于某种物品要选取多个，都可以由若干个2k个物品进行组合(即2进制数)。例如第i种物品要选10个，则10=23+21。这样第i种物品的个数为k=㏒2(m/wi)物品，是一个很大的改进。进一步,在计算k时,K=㏒2(j/wi),j为当前背包剩余空间。进一步fori:=1tondo//
7、动态规划，递推求fforj:=mdownto1dobeginifj>=w[i]then//背包容量够大f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])else//背包容量不足f[i,j]:=f[i-1,j];end;在这里为了使得每个物品只取1个或不取,采用了每次取j都是与i-1进行比较，实际上保存了每1步取不同j的值改进程序事实上，我们只关心剩余背包的最大值，也就是仅仅关心f(j),因此，在对f(j)更新时，只要背包容量可以，那么可以反复更新。程序如下：fori:=1tondo//动态
8、规划，递推求fforj:=0tomdobeginifj>=w[i]then//背包容量够大f[j]:=max(f[j-w[i]]+c[i],f[j])end;思考题1：机器分配M台设备，分给N个公司。若公司i获得j台设备，则能产生Aij效益问如何分配设备使得总效益最大？M<=15，N<=10。分析用机器数来做状态，数组f(i,j)
