动态规划-背包问题专题.ppt

动态规划- 背包问题及其变形
长沙市一中曹毅
回顾:动态规划的核心要素
基本概念:
阶段
状态
状态转移方程
使用条件:
最优子结构
无后效性
背包问题:
01背包问题
完全背包问题
多重背包问题
混合背包问题
二维费用的背包问题
分组背包问题
有依赖背包问题
01背包
有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
基本思路:对于第i件物品,我们有两个选择:放或者不放,用f[i][v]表示前i件物品恰放入容量为v的最大价值,于是有两种情况:
不放:f[i][v]=f[i-1][v]
放: f[i][v]=f[i-1][v-c[i]]+w[i]
最后取这两者的最大值
于是得出状态转移方程:
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
边界:f[1][0]=0(不装任何东西)
核心代码:
for i=1..n
for v=v..0
f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}
时空分析及优化
以上方法的时间和空间复杂度均为O(N*V),其中时间复杂度基本已经不能再优化了,但空间复杂度却可以优化到O(V)。
f[i][v]->f[v] ‘f[v]表示重量不超过V公斤的最大价值
数据:
10 4
重量价值求得:
2 1
3 3
4 5
7 9
f[1] 0
f[2] 1
f[3] 3
f[4] 5
f[5] 5
f[6] 6
f[7] 9
f[8] 9
f[9] 10
f[10] 12
完全背包问题
有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
区别:第i件物品可以无限装,01背包只能装一次
转换:f[v]=max{f[v],f[v-k*w[i]]+k*c[i]}
其中0<=k*w[i]<=v
for i=1..n
for v=0..v
f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}
01背包与完全背包对比
数据:
10 4
重量价值求得:
2 1
3 3
4 5
7 9
01背包
f[1] 0
f[2] 1
f[3] 3
f[4] 5
f[5] 5
f[6] 6
f[7] 9
f[8] 9
f[9] 10
f[10] 12
完全背包
f[1] 0
f[2] 1
f[3] 3
f[4] 5
f[5] 5
f[6] 6
f[7] 9
f[8] 10
f[9] 10
f[10] 12
为什么?
完全背包的优化:
:w[i]<=w[j] 且c[i]>=c[j]则去掉j物品(性价比低)
,核心思想:将第i种物品拆成若干个物品,其中每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,...,2^(k-1),n[i]-2^k+1,且k是满足n[i]-2^k+1>0的最大整数。例如,如果n[i]为13,就将这种物品分成系数分别为1,2,4,6的四件物品。目的还是转换为01背包问题。
多重背包问题:
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
分析:类似完全背包,k的取值范围有所变化
f[i][v]=max{f[i-1][v-k*c[i]]+ k*w[i]|0<=k<=n[i]}。复杂度是O(V*∑n[i])