这篇文章上次修改于 519 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

ACM程序课算法笔记4——背包问题

基本模型

给你一个容量为V的背包和若干种物品，在一定的限制条件下（每种物品都占用一定容量），问最多能放进多少价值的物品。

最典型最基本的动态规划问题，DP问题中状态的理解概念

有N件物品和一个容量为V的背包，知道每个物品的费用是cost[i]，价值是value[i]。求解将哪些物品装入背包可使价值总和最大。

01背包

特点：

每个物品只有一件，可以选择放或者不放

解题思路：

dp[i][v]表示前i个物品放入一个容量为v的背包可以获得的最大价值。

则可得状态转移方程

dp[i][v] = max(dp[i - 1][v - cost[i]] + value[i], dp[i - 1][v])

我们可以发现dp[i][v]只用到了dp[i - 1]，所以我们可以做出一维dp的优化

j循环从总容量递减到value[i]

dp[j] = max(dp[j], dp[j - cost[i]] + value[i])

思考：为什么要倒序？

先考虑第一次遍历，dp的值都是0，而后面的dp又依赖于前面的dp，保证了这个物品只会被取一次。

后续的第i次遍历，dp中的值只包含了前i-1个物品，后面的dp依赖于前面的dp，保证了新的dp只会最多包含一个第i件物品。

完全背包

特点：

一种物品可以取无数个

解题思路：

暴力转换思路：直接转换到01背包

可以考虑每件物品最多取几件，然后把这件物品复制n遍，便可变为01背包问题。

但是很容易爆效率，几件物品可能会膨胀到几万件。

优化思路：

和01背包类似，只需要将j循环从0到V

dp[j] = max(dp[j], dp[j - cost[i]] + value[i])

思考：为什么要正序？

从倒序的原因可以看出倒序是为了保证某个物品都只会被取一次，此时不放考虑一下正序的情况。

假如在正序情况第i次遍历，dp保存了前i-1物品的情况，如果前面的某次dp可以取第i件物品则取，后面的dp基于前面的dp，所以便可多次取第i件物品。即每次判断的时候都不考虑是否取过第i件物品，只考虑要不要取，取了值不值得。

填满背包

特点：

要求背包的容量要全部利用，不能有空余空间。

解题思路：

既然要求有空余空间，那么必然就有多种空间情况是非法的，一旦该方案非法，我们可以设置为-1，然后后面的dp依赖于前面的dp，每个dp只需要考虑两种情况（新增第i件物品和不增第i件物品），如果这两种情况都非法，则这个dp也非法，如果不非法则取用。

多重背包

一种物品可以取最多C个（不是一个也不是无数个）

解题思路：

暴力转换思路：直接转换到01背包

同理易得出，应该很好理解。

优化转换思路：优化转换到01背包

由于数可以转为二进制数，然后分开相加

例如 15 = 1 + 2 + 4 + 8

0~15都可以由1 2 4 8自由组合出来。

我们便把最多C个物品转为多个2次幂的数相加即可，多余的数单独一组，例如

18 = 1 + 2 + 4 + 8 + 3

二进制优化代码示例：

int t = 1;
while (x>=t) {
    v[cnt] = a*t;
    c[cnt++] = b*t;
    x -= t;
    t <<= 1;
}
if(x){
    v[cnt] = a*x;
    c[cnt++] = b*x;
}

二维费用背包

特点：

一个物品的占用两种费用，比如一件物品不仅占用空间，也有一定重量，给出最大空间和最大重量，求最大价值。

解题思路：

背包问题利用的dp储存利用的下标实际上就是状态，此时多了一个重量状态，同理只要多添加一维的空间即可。

解法同理。

状态转移方程：

f[i][v][u]=max(f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i])

Mai Icy