2资源背包动态规划.ppt.ppt

背包类动态规划问题
长沙市雅礼中学朱全民
经典的背包问题(01背包)
有N件物品;
第i件物品Wi公斤;
第i件物品价值Ci元;
现有一辆载重M公斤的卡车;
问选取装载哪些物品,使得卡车运送的总价值最大?
搜索法
对于每种物品,要么装上卡车,要么不装,因此,N种物品的装箱方案共有2N种。
按每种物品进行搜索,方法如下:
对第i种物品进行搜索
如果所有的物品都搜索完,则更新最优解
如果当前的估计达不到最优解,则回溯
如果第i种物品能放,则放,并标记,否则选下一个物品
清除标记
回溯
动态规划
可以按每个物品进行规划,同样每种物品有选和不选两种选择
设F(i,j)表示前i件物品载重为j的最大效益,则有
1<=i<=N, 0<=j<=N
初值:F(0,j)=0
F(N,M)即答案
显然时间复杂度为O(NM)
主程序如下
for i:=1 to m do f[0,i]:=0; //初始化
for i:=1 to n do f[i,0]:=0;
for i:=1 to n do // 动态规划,递推求f
for j:=1 to m do
begin
if j>=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;
满背包问题(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种方案
仅装载主件
装载主件+第1个附件
装载主件+第2个附件
装载主件+2个附件
由于上述4种并列,这是几种不同的决策同时规划即可
动态规划
设F(i,j)表示前i件物品背包为j的最优解,则有,
1<=i<=N, 0<=j<=M
时间复杂度O(NM)