01背包和完全背包

最近学习《背包问题九讲》,对0-1背包和完全背包有了新的认识。最新版本请访问 https://github.com/tianyicui/pack 查阅。

1.01背包问题

关于01背包问题的方程式如下，此时的时间复杂度位O(NV)，N为状态数目，V为背包总大小，空间复杂度位O(NV)：

F [i, v] = max {F [i − 1, v], F [i − 1, v − C i ] + W i }

通过复用DP矩阵，可以将之转换为O(V)，V为背包大小，此时的伪代码为：

F [0..V ] ←0
for i ← 1 to N
    for v ← V to C i
          F [v] ← max {F [v], F [v − C i ] + W i }

2.完全背包

这个问题非常类似于01背包问题,所不同的是每种物品有无限件。也就
是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有
取 0 件、取 1 件、取 2 件......直至取 ⌊V /C i ⌋ 件等许多种。
如果仍然按照解01背包时的思路,令 F [i, v] 表示前 i 种物品恰放入一个容
量为 v 的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程,像这样:

F [i, v] = max (F [i − 1, v], F [i, v − C i ] + W i )

其O(V)的伪代码如下：

F [0..V ] ←0
    for i ← 1 to N
        for v ← C i to V
              F [v] ← max (F [v], F [v − C i ] + W i )

3.背包问题应用

第一节已经给出了01背包在O(V)条件下的伪代码，这里给出其O(NV)状态下的伪代码：

F [0, 0..V ] ← 0
    for i ← 1 to N
        for v ← C i to V
            F [i, v] ← max {F [i − 1, v], F [i − 1, v − C i ] + W i }

上面可以看到，从i-1状态下变迁过来的状态之间是隔离的，每个i状态和i-1状态相关。
而完全背包则不是这样，按照F [i, v] = max {F [i − 1, v − kC i ] + kW i | 0 ≤ kC i ≤ v}的转移方程获得如下代码：

F[0][] ← {0}  
F[][0] ← {0}  
for i←1 to N  
    do for j←1 to V  
        do for k←0 to j/C[i]  
           if(j >= k*C[i])  
                then F[i][k] ← max(F[i][k],F[i-1][j-k*C[i]]+k*W[i])  
return F[N][V] 

如此情况下的时间复杂度为O(NV∑(j/C[i]))。要获得O(VN)时间复杂度的完全背包解法，需要用到第二节使用的递推关系式，其伪代码第二节也已经介绍了。
这里我使用LeetCode上343. Integer Break 来讲解。
第一种，不服用DP矩阵。

public int integerBreak(int n) {
        if (n <= 1) return 0;
        int[][] dp = new int[n + 1][n + 1];
        dp[0][1] =1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (j < i) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j],
                            Math.max(dp[i][j - i], j - i) *
                                    Math.max(dp[i][i], i));
                }
            }
        }
        return dp[n][n];
    }

第二种，复用DP矩阵。

    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
       dp[1] = 1;
       for(int i = 2; i <= n; i ++) {
           for(int j = 1; j < i; j ++) {
               dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));
           }
       }
       return dp[n];
    }

4.总结

（Tips：O(NV)时间复杂度）
× 01背包的状态迁移是前后无关的，i状态由i-1状态迁移而来，因此，必须保证前状态的状态无法影响后状态。因此，在O(V)空间复杂度下，必须从后往前迁移状态，防止状态叠加。
× 完全背包的状态是需要叠加的。因此在O(NV)空间复杂度状态下的状态迁移，需要收到i状态下其他背包的影响。O(V)空间复杂度下，则从前向后推移状态。