背包问题知识总结

背包问题在不同的资料中可能分为不同的类别,在学习背包问题时,我们将背包分为以下几类:01背包,完全背包,多重背包,分组背包。
先一个一个说起:
一、01背包:
有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
这是求最大利润值的01背包问题,01背包是最基础的背包问题,其中0,1的由来就是放或不放两种选择的问题(物品只有一件,对于每种物品都是两种选择。)
根据问题我们便可以建立状态转移方程:
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
其中f[i][v]表示前i件物品恰好放入一个容量为v的背包可获得的最大价值(f[i][v]在第i件物品的选择上对价值总和而言还与前i-1件物品的价值总和有关,再根据第i件物品是否选择可列出方程)
优化空间复杂度:
上面的状态转移方程为二维数组,当数据量较大时容易占用大量内存空间,如果我们能够将二维数组转化为一维数组会节省大量空间:我们可以通过规律发现每次第i件物品都只与前i-1件物品有关,所以我们不在写出i,i-1之间的关系,将它们省略掉,写成:f[v]=max{f[v],f[v-c[i]]+w[i]}; 这里我们仍默认i从1到N的循环关系。
对于背包问题,还有一处细节(要求),就是看背包是否装满:初始化细节:若要求恰好装满背包,初始化时除了f[0]为0其它f[1…V]均设为-∞,-∞表示背包在此时并未装满,并没有达到要求。若没有要求必须把背包装满,初始化时将f[0…V]全部设为0
二、完全背包
有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
完全背包与01背包唯一的区别就是物品充足,可以随意装入,当然我们可以转化为01背包:考虑到第i种物品最多选V/c[i]件,于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品,然后求解这个01背包问题 。f[i][v]=max{f[i-1][v-kc[i]]+kw[i]|k=0…m};m=V/c[i];即f[v]=max{f[v],f[v-cost]+weight} 。
此处v的循环次序和01背包的循环次序不同,01背包是V…0;完全背包是0…V。
三、多重背包:
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大 。
相对于完全背包物品的数量进行了限制,基本的方程只需将完全背包问题的方程略微一改即可,因为对于第 i 种物品有 n[i]+1 种策略:取 0 件,取 1 件… 取 n[i] 件。
令 f[i][v] 表示前 i 种物品恰放入一个容量为 v 的背包的最大权值, 则有状态转移方程:
f[i][v]=max{f[i-1][v-kc[i]]+kw[i]|0<=k<=n[i]}
四、分组背包:
这个问题变成了每组物品有若干种策略:是选择本组的某一件,还是一件都不选。
状态方程:
for 所有的组k
for v=V…0
for 所有的i属于组k
“for v=V…0 ”这一层循环必须在“ for 所有的 i 属于组 k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。
f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于组k}
压缩优化后:
f[v]=max{f[v],f[v-c[i]]+w[i]}
在解决这些问题时,我们首先要确定是哪一类背包问题,这基本上也很容易看出,然后套用该背包问题的算法模板形式就容易解决问题了,不过有的题目似乎是背包的混合问题,当然这类问题比较难,需要我们更加深入的思考。