背包问题(上)

此博客根据背包九讲1-3章整理编写而成，记录学习总结。
一句话：01逆序，完全正序

0-1背包问题

题目

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

思路

定义子问题状态: $F[i,v]$为前$i$件物品放入一个容量为$v$的背包可以获得的最大价值。这里的前$i$件物品包括第$i$件物品。
状态转移方程：

$F[i,v]=\max\{F[i-1,v], F[i-1,v-C_i]+W_i\}$

这个状态转移方程非常好理解，对于第$i$件物品，我们只有放与不放两种选项，如果不放，那么这个背包的价值就是和前$i-1$件物品放入背包的价值一样，即$F[i-1,v]$；如果放的话，那么这个背包的价值就是前$i-1$件物品放入容量为$v-C_i$的背包的价值再加上当前物品的价值$W_i$。
接下来的问题就是如何填充这个二维数组$F_{N\times V}$。首先我们要看到，由于我们根本不清楚这个$V$有多大，$C$里面有哪些数，所以我们在迭代时一定要保证$F[i-1]$里所有的entry都是已知的，也就是前$i$件物品在所有可能的背包容量下的价值。
伪代码：

代码实现：

def ZeroOnePackBasic(N, V, C, W):
    Vs = V + 1
    Ns = N + 1
    dp = [[0] * (Vs) for _ in range(Ns)]
    for i in range(1, N+1):
        for v in range(C[i-1], Vs):
            dp[i][v] = max(dp[i-1][v], dp[i-1][v-C[i-1]]+W[i-1])
    return dp[N][V]

边界点1：$v=0,i=0$, 虽然我们的容量为$V$，物品数目为$N$，但我们有$V+1$，$N+1$种物品（包含0容量和前0件物品）。

边界点2：$v<C_i$，易知当v小于$C_i$时，根本无法将第$i$件物品放入背包，所以我们的遍历空间为$C_i...V$。

优化空间复杂度

实用一个数组$F[0...V]$来代替二维数组，原因在于状态转移方程只和上一次迭代的结果，也就是$F[i-1, 0...V]$相关。所以我们可以基于上一个$F_{i-1}$来更新当前$F_i$。然而，我们必须逆序计算$F[v]$, $v \leftarrow V...0$，原因在于这样可以保证$v-C_i$之前的entry是$F_{i-1}$未更新的。

伪代码：

代码实现:

def ZeroOnePackOpt(N, V, C, W):
    Vs = V + 1
    Ns = N + 1
    dp = [0] * Vs
    for i in range(1, Ns):
        for v in range(Vs-1, C[i-1]-1, -1):
            dp[v] = max(dp[v], dp[v-C[i-1]]+W[i-1])
    return dp[V]

题目变种

要求恰好装满背包时的最优解。

这种情况我们要重新定义一下子问题状态: $F[i,v]$为前$i$件物品放入一个容量为$v$的背包恰好装满时可以获得的最大价值。这里的前$i$件物品包括第$i$件物品。

也就是说我们初始化的时候需要重新定义$F$的合法数值，当$i=0$，只有$v=0$，才能满足恰好装满的条件，也就是没有任何物品放入背包，背包已满。$v$的其他取值都初始化为$-\infty$，也就是标记为不合法。

代码实现:

def ZeroOnePackFull(N, V, C, W):
    Vs = V + 1
    Ns = N + 1
    dp = [float('-inf')] * Vs
    dp[0] = 0
    for i in range(1, Ns):
        for v in range(Vs-1, C[i-1]-1, -1):
            dp[v] = max(dp[v], dp[v-C[i-1]]+W[i-1])
    return dp[V]

复杂度

时间复杂度为$O(VN)$

优化后的空间复杂度为$O(V)$

494. 目标和

乍一看这题和0-1背包问题一点关系都没有，但是实际上还是一个背包问题。可以讲这一组数据分为两组，正数组和负数组。分别记为left和right

$\begin{aligned} left - right = target \\ left - (sum - left) = target \\ left = \frac{target+sum}{2} \end{aligned}$

如果left不是整数的话其实就代表这无解，然后我们就可以把这题转换成一个塞满整个背包有多少种方法的0-1背包问题。

1. 定义dp状态
   $dp[i,v]$为前i个物品能够装满容量为v的背包的方法数量
2. 状态转移

$dp[i,v] = dp[i-1,v] + dp[i-1,v-C_i]$

$dp[i-1,v]$表示不放第i个物品，前i-1已经装满v的组合数
$dp[i-1,v-C_i]$表示放第i个物品的组合数，前i-1刚好还差$C_i$大小的第i个物品
3. 优化空间
由于都是从i-1转换而来，所以i-1相当于当前数组还未更新的状态，于是有dp[v] = dp[v] + dp[v-nums[i]];。

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = sum(nums);
        if ((sum + S) % 2 == 1 || S > 1000) {
            return 0;
        }
        int left = (sum + S) / 2;
        int[] dp = new int[left+1];
        dp[0] = 1;
        for (int i=0; i < nums.length; i++) {
            for (int v=left; v >= num; v--) {
                dp[v] = dp[v] + dp[v-nums[i]];
            }
        }
        return dp[left];
    }

    public int sum(int[] nums) {
        int ret = 0;
        for (int e: nums) 
            ret += e;
        return ret;
    }
}

完全背包问题

题目

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

基本思路

这个问题非常类似于0-1背包问题，所不同的是每种物品都有无限件。所以每种物品的取件数有$\lfloor V/C_i \rfloor$种选择。

现在我们仍旧定义原来的子问题$F[i,v]$，只不过加上了可以重复取件的条件。

于是乎状态转移方程需要发生改变:

$F[i,v]=\max\{F[i-1,v-kC_i] + kW_i | 0 \leq kC_i \leq v\}$

这个和0-1背包问题一样有$O(VN)$个状态需要求解，但是求解每个状态的时间不是常数而是$O(\lfloor \frac{v}{C_i}\rfloor)$，总的时间复杂度为$O(NV\sum^N_{i=1}{\frac{V}{C_i}})$

def CompletePackBasic(N, V, C, W):
    Vs = V + 1
    Ns = N + 1
    dp = [0] * Vs
    for i in range(1, Ns):
        for v in range(Vs-1, C[i-1]-1, -1):
            tmp = []
            for k in range(0, (v // C[i-1])+1):
                tmp.append(dp[v-k*C[i-1]]+k*W[i-1])
            dp[v] = max(tmp)
    return dp[V]

优化

优化1 对数据进行预处理：

首先将费用大于 V 的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以差不多用$O(V +N)$地完成这个优化，除非重复费用的物品过多。

优化2 转化为01背包问题：

这个优化非常刁钻，考虑到第$i$种物品最多选 $⌊V/C_i⌋$ 件，于是可以把第$i$种物品转化为$⌊V/C_i⌋$件费用及价值均不变的物品。比如现有

$\begin{aligned} N &= 4 \\ V &= 10 \\ C &= [10, 6, 3, 4] \\ W &= [10, 7, 6, 5] \\ \end{aligned}$

我们可以将其转换为如下的0-1背包问题

$\begin{aligned} N &= 7 \\ V &= 10 \\ C &= [10,6,3,3,3,4,4] \\ W &= [10,7,6,6,6,5,5] \\ \end{aligned}$

还有一种更骚的操作是：把第$i$种物品拆成费用为$C_i2^k$、价值为$W_i2^k$的若干件物品，其中$k$取遍满足$C_i2^k≤V$的非负整数。不管最优策略选几件第$i $种物品，总可以表示成若干个不同$2^k$物品的和。这样一来就把每种物品拆成$O(\log ⌊V/Ci⌋)$件物品，是一个很大的改进。用之前的例子，我们可以将其装化为如下的01背包问题

$\begin{aligned} N &= 6 \\ V &= 10 \\ C &= [10, 6, 3, 6, 4,8] \\ W &= [10, 7, 6, 12,5,10] \\ \end{aligned}$

为什么可以如此转换呢？原因在于$2^n-1=\sum_{i=0}^{n-1}2^{i}$，我们可以看到在上一个简单的01背包问题转换操作中，取3个费用为3价值为6的情况是用3个相同价值相同费用的物品实现的，而在这个转换方法中这种情况是由取1个费用为3和1个费用为6的物品实现的，大大减少了遍历的次数。

优化3 O(VN) 改变遍历次序

伪代码：

我们可以发现，这段伪代码和01背包问题仅仅只有$v$的循环次序不同，现在采用增序递增的方式更新子状态。原因在于，此时我们需要一个可能已选入第$i$种物品的子结果$F[i,v-C_i]$。此时的状态转移方程为:

$F[i,v]=\max\{F[i-1,v],F[i,v-C_i]+W_i\}$

$F[i-1,v]$：不放入第$i$件物品

$F[i,v-C_i]$: 上一次放了第$i$件物品时的价值加上这次放第$i$件物品

此时的空间复杂度为$O(V)$，时间复杂度依然为$O(VN)$。

def CompletePackVN(N, V, C, W):
    Vs = V + 1
    Ns = N + 1
    dp = [0] * Vs
    for i in range(1, Ns):
        for v in range(C[i-1], Vs):
            dp[v] = max(dp[v], dp[v-C[i-1]]+W[i-1])
    return dp[V]

多重背包问题

题目

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

基本思路

这题和完全背包问题十分相似，在这里对于第$i$种物品，我们有$M_i+1$种策略：取0件，取1件，…，取$M_i$件；而在完全背包问题种我们有$\lfloor \frac{V}{C_i}\rfloor +1$种取法。所以我们只要稍微修改一下状态转移方程即可：

$F[i,v]=\max\{F[i-1,v-k*C_i]+k*W_i|0\leq k \leq M_i\}$

此时的时间复杂的为$O(V\sum_{i=1}^{N}M_i)$。

转化为01背包问题

和之前的完全背包问题一样，多重背包问题也可以通过拆分转换为01背包问题。

如完全背包问题中的优化1一样，我们可以将第$i$种物品拆分成$M_i$件相同费用相投价值的物品。此时的时间复杂度依然是$O(V\sum_{i=1}^{N}M_i)$。

实现代码：

def MultiPackBasic(N, V, C, W, M):
    '''
    将多重背包问题简单转换成01背包问题
    '''
    for i in range(N):
        m = M[i] - 1
        C += [C[i]] * m
        W += [W[i]] * m
        N += m
    Vs = V + 1 
    Ns = N + 1
    dp = [0] * Vs
    for i in range(Ns):
        for v in range(Vs-1, C[i-1]-1, -1):
            dp[v] = max(dp[v], dp[v-C[i-1]]+W[i-1])
    return dp[-1]

同样的，我们还可按照之前优化1中的第二种方法来拆分：

将第$i$种物品拆分成若干个01背包中的物品，这些物品的费用和价值均是原来的费用和价值乘以这个系数。这些系数分别为$1,2,..,2^k$且$k$是满足$2^k\leq M_i$的最大整数。例如，如果$M_i$为$13$，则相应的$k = 3$，这种最多取$13$件的物品应被分成系数分别为$1, 2, 4, 8$的四件物品。

为什么我这里采用的系数和背包九讲里的系数不同？因为我按照的是之前完全背包问题的拆分方法，也就是拆到系数大到允许的物品件数为止。个人认为，这样的拆分方法更容易理解，也更容易实现和证明。

代码实现：

def MultiPackBinary(N, V, C, W, M):
    '''
    将多重背包问题利用二进制的特性转换成01背包问题
    '''
    for i in range(N):
        Mi = M[i]
        k = 2
        while k <= Mi:
            N += 1
            W += [W[i] * k]
            C += [C[i] * k]
            k *= 2
    Vs = V + 1 
    Ns = N + 1
    dp = [0] * Vs
    for i in range(1, Ns):
        for v in range(Vs-1, C[i-1]-1, -1):
            dp[v] = max(dp[v], dp[v-C[i-1]]+W[i-1])
    return dp[-1]

时间复杂度：$O(V\sum_{i=1}^{N}\log{M_i})$；空间复杂度：$O(V)$ （我们可以筛掉不可能的取件数选项）。

二进制拆分法的数学证明

本证明由复旦某数学系大佬提供

$Proposition$: For any positive integer $m \leq 2^{n}-1$，there exists a set $S \subseteq \{0,1,2,...,n-1\}$ and $S\neq \phi$ such that $m=\sum_{i\in S}2^{i}$.

$Proof$:

It is obvious to get there are totally $2^n-1$ kinds of $S$, because the number of permutations is

$\sum_{i=1}^n{n \choose i}=2^n-1$

Also, we can find the maximum of $m$ is $2^n - 1$ and the minimum is $1$. There are totally $2^n-1$, and the range of the sum is from $1$ to $2^n-1$. It means that as long as we prove the sum of each $S$ is unique, we can prove the proposition. In mathematical words, for any $S_i,S_j$ where $i\neq j$, $\sum_{k\in S_i}2^k \neq \sum_{k \in S_j}2^k$.

Given two different sets $S_i$ and $S_j$, we can get $G_i = S_i-S_j$ and $G_j=S_j-S_i$. WLOG, we only need to prove that $\sum_{k\in G_i}2^k \neq \sum_{k \in G_j}2^k$, for any $G_i,G_j$ where $i\neq j$.

First situation, either $G_i$ or $G_j$ contains the index $0$. WLOG, we assume $G_i$ contains the index $0$. Then the component sum of $G_i$ is odd, while the component of $G_j$ is even. Therefore, they must be different.

$\sum_{k \in G_i}{2^k}=1+\sum_{k\neq 0, k \in G_i}{2^k} \neq \sum_{k\in G_j}2^k$

Second situation, neither $G_i$ or $G_j$ contains the index 0. We defined that $G_i=\{2^{i_k}|i_k<i_{k+1},k=1,2,...,p\}$ where $p$ is the number of entries in $G_i$, similarly, $G_j=\{2^{j_k}|j_k<j_{k+1},k=1,2,...,q\}$ where $q$ is the number of entries in $G_j$. WLOG, we set $i_1 < j_1$.

We assume that the internal summations of $G_i$ and $G_j$ are equal, we can get the following equation:

$\begin{aligned} \sum_{k \in G_i}2^k=\sum_{k \in G_j}2^k \\ 2^{i_1}+2^{i_2}+...+2^{i_p} = 2^{j_1}+2^{j_2}+...+2^{j_q} \\ 1+2^{i_2-i_1}+...+2^{i_p-i_1}=2^{j_1-i_1}+2^{j_2-i_1}+...+2^{j_q-i_1} \end{aligned}$

Since $G_i \cap G_j=\phi$ and neither $G_i$ or $G_j$ contains the index of $0$, therefore the left-hand side of equation is odd and the right-hand side is even, which contradicts the previous assumption of equivalence of internal summation of $G_i$ and $G_j$.

Thus, we can prove that the summation of any $S$ is unique, which further proves one-to-one mapping relation that for any positive integer $m \leq 2^{n}-1$，there exists a unique set $S \subseteq \{0,1,2,...,n-1\}$ and $S\neq \phi$ such that $m=\sum_{i\in S}2^{i}$.

实际上我们可以通过二进制来看出一些端倪，比如

$\begin{aligned}11010110_{2} = \\ & 10000000_2+ \\ & 01000000_2+ \\ & 00010000_2+ \\ & 00000100_2 + \\ & 00000010_2 \end{aligned}$

我们可以看到，任意一个整数都可以用二进制来表示，然后它的位数计算其实就是我们的拆分方式。

可行性问题的$O(VN)$算法

如果问题考察的是"每种有若干件的物品能否填满给定容量的背包"，只要考虑填满背包的可行性，不需考虑没见物品的价值时，多重背包问题可以有$O(VN)$复杂度的算法。

事实上，0-1背包问题的装满可行性算法就是$O(VN)$，所以比较直观的想法是利用上述拆分法将多重背包问题转换成0-1背包问题，然后解决，不过此时的时间复杂度是$O(V\sum{M_i})$。

所以我们需要对子状态进行重新定义：

$F[i,v]$表示用前$i$种物品填满容量为$v$的背包后，还剩下多少个第$i$种物品可用。定义$F[i,V]=-1$为不合法，即未填满。所以我们只要判断前$i$物品填满容量为$V$的背包后是否等于$-1$就可以知道能否装满了。

伪代码：

代码实现：

def canFullPack(N, V, C, M):
    Ns = N + 1
    Vs = V + 1
    dp = [-1] * Vs
    dp[0] = 0
    for i in range(1, Ns):
        for v in range(V):
            if dp[v] >= 0:
                dp[v] = M[i-1]
            elif dp[v] == -1:
                dp[v] = -1
        for v in range(C[i-1], Vs):
            dp[v] = max(dp[v-C[i-1]]-1, dp[v])
    return dp[-1] >= 0

第二层循环中的第一层循环是初始化当前物品的$M_i$在各个合法entry中的值，表明当前所有塞满的背包剩下最多$M_i$的第$i$件物品；

第二层循环中的第二层循环是便是状态转移方程的实现，

$F[i,v] = \max (F[i,v-C_i]-1,F[i,v])$

为什么要定义最多剩下呢？这是一种贪婪的想法，我们需要尽可能的为后面的装填留更多的物品。

例题

322. 零钱兑换

咱们接下来看一到经典例题，零钱兑换。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        Ns = len(coins) + 1
        Vs = amount + 1
        dp = [float('inf')] * Vs
        dp[0] = 0
        for i in range(1, Ns):
            for v in range(coins[i-1], Vs):
                dp[v] = min(dp[v], dp[v-coins[i-1]]+1)
        return -1 if dp[-1] == float('inf') else dp[-1]

这道题其实也可以转换成背包问题，我们把amount看作这个背包的容量，硬币就是价值为$1$的物品，硬币的面值看作每件物品的费用。为什么我们把硬币的价值作为$1$来处理呢？其实我们可以定义子状态$F[i,v]$为前$i$种物品要装满容量为$v$的背包至少所需要的件数，这和我们把硬币的价值看作$1$其实是一样的。