LeetCode-Day42

背包问题的详解

1. 01背包问题

题目：

有N 件物品和一个容量为V 的背包。放入第i件物品耗费的费用是$C_i$，得到的价值是$W_i$。求解将哪些物品装入背包可使价值总和最大。

基本思路：

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或者不放

用子问题定义状态，即f[i,v]表示前i间物品恰放入一个容量为v的背包可以获得的最大值。则其状态转移方程便是$f[i,v] = max(F[i - 1,v], F[i - 1, v - C_i] + W_i)$

伪代码如下：

优化空间复杂度：

以上方法的时间和空间复杂度均为$O(VN)$，其中时间复杂度已经不能再优化了，但是空间复杂度却可以优化到$O(V)$

我们可以将代码写成下面这种形式：

首先，这里本来是个二维数组，但是由于我们每次更新当前行的时候，只用到了前一行的数据，因此可以变成一个一维数组。

这里注意到：$v \leftarrow V \text { to } C_{i}$

为什么要这样写呢？

因为当我们变成一维数组的时候，在进行状态更新的时候，当前的状态依赖于前面的状态，如图：


更新完之后，还得写回当前的位置，为了不影响后面的操作，所以这里需要倒过来写

初始化的细节问题：

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0] = 0，其他F[1...V]均设为$-\infty$。这样就能保证最终得到的f[V]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应将F[0...V]全部设为0

为什么呢？可以这样理解：初始化的F数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么也不装且价值为0的情况下被“恰好装满”，其他容量的背包均没有合法的解，属于未定义的状态，应该就被赋值为$-\infty$。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就是全部为0了

2. 完全背包问题

题目：

有$N$ 种物品和一个容量为$V $的背包，每种物品都有无限件可用。放入第i 种物品的费用是$C_i$，价值是$W_i$。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

常规思路：

常规思路应该写出这样的表达式：

$F[i, v] = max(F[i - 1,v - k * (C_i)] + kW_i), 0 \le kC_i \le v$

一个简单有效的优化：

完全背包问题有一个很简单有效的优化，是这样的：若两件物品$i$、$j$ 满足 $C_i \le C_j$，且$W_i \ge W_j$，则可以直接将物品j去掉，不用考虑。这个优化的正确性是显然的：任何情况下都可以将价值小费用高的j换成物美价廉的i，得到的方案至少不会更差。

$O(VN)$的算法：

伪代码：

你会发现，这个伪代码与01背包的伪代码只有v的循环次序不同而已。

为什么这个方法可行呢？我们先来看看原来为什么需要逆序？


因为我们怕改变当前的值会影响到后面，但是现在我们恰恰需要这种影响，因为这个时候，我们的物品不止一件了，可以无限的放进背包，而且这种影响可以表示为：我在已经放入k个i物品之后，在放入一件i物品不会不会使得我的价值更大呢？

3. 多重背包问题

题目：

有N 种物品和一个容量为$V$ 的背包。第$i$ 种物品最多有$M_i$ 件可用，每件耗费的空间是$C_i$，价值是$W_i$。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

基本算法：

$F[i, v] = max(F[i - 1,v - k * (C_i)] + kW_i), 0 \le k \le M_i$

转换为01背包问题：

k <- 1
while(k < M) 
	ZeroOnePack(kC, kW)
	M <- M - k
	k <- 2k
ZeroOnePack(CM, WM)

377. 组合总和IV

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。

思路：实际上就是一个完全背包的问题

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        if(nums.size() == 0) {
            return 0;
        }
        int dp[target + 1] = {0};
        dp[0] = 1;
        for(int i = 1;i <= target;i++) {
            for(int num : nums) {
                if(i >= num) {
                    dp[i] = dp[i] >= INT_MAX - dp[i - num] ? 0 : dp[i] + dp[i - num];
                }
            }
        }
        return  dp[target];
    }
};

这里需要注意有可能会出现int范围爆炸的问题。所以需要提前判断一下！