第六讲动态规划背包问题.ppt

背包类动态规划问题
1
经典的背包问题(01背包)
有N件物品;
第i件物品Wi公斤;
第i件物品价值Ci元;
现有一辆载重M公斤的卡车;
问选取装载哪些物品,使得卡车运送的总价值最大?
2
动态规划
可以按每个物品进行规划,同样每种物品有选和不选两种选择
设F(i,j)表示前i件物品载重为j的最大效益,则有
1<=i<=N, 0<=j<=N
初值:F(0,j)=0
F(N,M)即答案
显然时间复杂度为O(NM)
3
主程序如下
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;
4
满背包问题(01背包)
有N件物品;
第i件物品Wi公斤;
第i件物品价值Ci元;
现有一辆载重M公斤的卡车;
问选取装载哪些物品,使得卡车开车正好装满时,运送的总价值最大?
若无法装满卡车,则输出无解。
5
动态规划
设F(i,j)表示前i件物品背包为j的最大效益,则有
1<=i<=N, 0<=j<=N
初值:F(0,j)=0, F(1,j)= -∞
F(N,M)即答案
显然时间复杂度为O(NM)
6
动态规划
设F(i,j)表示前i件物品背包为j的最优解,则有,
1<=i<=N, 0<=j<=M
时间复杂度O(NM)
9
多层背包问题
有N件物品;
第i件物品Wi公斤;
第i件物品价值Ci元;
现有一辆载重M公斤的卡车;
第i件物品限制最多只能取Xi个;
问选取装载哪些物品,使得卡车运送的总价值最大?
10