【背包问题九讲】第一讲：01背包问题（含Java实现代码）

左手的ㄟ右手 2024-02-22 09:53 44阅读 0赞

#### 文章目录 ####

*  一、题目
 *  二、基本思路
 *   *  2.1 讲解
     *  2.2 代码
 *  三、优化空间复杂度
 *   *  3.1 讲解
     *  3.2 代码
 *  四、初始化的细节问题
 *  五、一个常数优化
 *  六、小结

## 一、题目 ##

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

## 二、基本思路 ##

### 2.1 讲解 ###

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即  F \[ i , v \] F\[i, v\] F\[i,v\] 表示前  i i i 件物品放入一个容量为  v v v 的背包可以获得的最大价值。则其状态转移方程便是：  
 F \[ i , v \] = m a x \{ F \[ i − 1 , v \] , F \[ i − 1 , v − C i \] + W i \} F\[i, v\] = max\\\{F\[i − 1, v\], F\[i − 1, v − C\_i\] + W\_i\\\} F\[i,v\]=max\{ F\[i−1,v\],F\[i−1,v−Ci\]\+Wi\}这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：**前  i i i 件物品放入一个容量为  v v v 的背包可以获得的最大价值**这个子问题：

对于  F \[ i , v \] F\[i, v\] F\[i,v\]，若只考虑第  i i i 件物品放与不放，则有两种情况：

1.  **不放**第  i i i 件物品：则这种情况可以获得的最大价值等价于 **“前  i − 1 i-1 i−1 件物品放入一个容量为  v v v 的背包可以获得的最大价值”**
    
    即： F \[ i , v \] = F \[ i − 1 , v \] F\[i, v\] = F\[i-1, v\] F\[i,v\]=F\[i−1,v\]
2.  **放** 第  i i i 件物品：则这种情况可以获得的最大价值等价于 **“前  i − 1 i-1 i−1 件物品放入一个容量为  v − C i v-C\_i v−Ci 的背包可以获得的最大价值 与第  i i i 件物品的价值之和”**
    
    即： F \[ i , v \] = F \[ i − 1 , v − C i \] + W i F\[i, v\] = F\[i-1, v-C\_i\]+W\_i F\[i,v\]=F\[i−1,v−Ci\]\+Wi
3.  我们需要的最大价值是上面两种情况的**最大值**，故： F \[ i , v \] = m a x \{ F \[ i − 1 , v \] , F \[ i − 1 , v − C i \] + W i \} F\[i, v\] = max\\\{F\[i − 1, v\], F\[i − 1, v − C\_i\] + W\_i\\\} F\[i,v\]=max\{ F\[i−1,v\],F\[i−1,v−Ci\]\+Wi\}

**伪代码**如下：  
 F \[ 0 , 0 ⋯ V \] ← 0 f o r    i    ←    1    t o    N f o r    v    ←    C i    t o    V F \[ i , v \]    ←    m a x \{ F \[ i − 1 , v \] , F \[ i − 1 , v − C i \] + W i \} \\begin\{aligned\} &F\[0, 0\\cdots V\] \\leftarrow 0 \\\\ &for \\; i \\; \\leftarrow \\; 1 \\; to \\; N \\\\ &\\qquad for \\; v \\; \\leftarrow \\; C\_i \\; to \\; V \\\\ &\\qquad\\qquad F\[i, v\] \\; \\leftarrow \\; max\\\{F\[i − 1, v\], F\[i − 1, v − C\_i\] + W\_i\\\} \\end\{aligned\} F\[0,0⋯V\]←0fori←1toNforv←CitoVF\[i,v\]←max\{ F\[i−1,v\],F\[i−1,v−Ci\]\+Wi\}

### 2.2 代码 ###

**Java代码**如下，这里我给出了**完整的包含输入输出**的代码，以方便大家理解。后续代码将只给出 `problem()` 方法。

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner in = new Scanner(System.in);
            while (in.hasNext()) {
        
                // 输入
                int N = in.nextInt();   // 物品数量
                int V = in.nextInt();   // 背包容量
                int[] C = new int[N];   // N件物品的费用（体积）
                int[] W = new int[N];   // N件物品的价值
                for (int i = 0; i < C.length; i++) {
        
                    C[i] = in.nextInt();
                }
                for (int i = 0; i < W.length; i++) {
        
                    W[i] = in.nextInt();
                }
    
                // 调用
                int ans = problem(N, V, C, W);
                System.out.println(ans);
            }
        }
    
        // 01背包问题
        public static int problem(int N, int V, int[] C, int[] W){
        
            int[][] dp = new int[N+1][V+1];
            for (int i = 1; i <= N; i++) {
        
                for (int j = C[i-1]; j <= V; j++) {
        
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-C[i-1]] + W[i-1]);
                }
            }
            return dp[N][V];
        }
    
    }

## 三、优化空间复杂度 ##

### 3.1 讲解 ###

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

上一小节基本思路中，主循环 `for (int i = 1; i <= N; i++)` 依次考察每一件物品放入与不放入的情况，并依次修改 `dp[][]` 数组每一行的元素。通过观察可以发现，**每一行元素的修改，都只与上一行元素的值有关**。那我们是否可以只存储一行的元素的值，并在这一行中**原地执行**算法呢？

当然是可以的！此时  F \[ N \] \[ V \] F\[N\]\[V\] F\[N\]\[V\] 将简化为  F \[ V \] F\[V\] F\[V\]，我们只需要在每一行中**以递减顺序计算  F \[ v \] F\[v\] F\[v\] 的值**。在第  i i i 次循环时，当前的 F \[ v \] F\[v\] F\[v\] 是上一次循环时计算得到的值，相当于上一小节中的  F \[ i − 1 \] \[ v \] F\[i-1\]\[v\] F\[i−1\]\[v\]，而我们所需要计算的  F \[ v \] F\[v\] F\[v\] 相当于上一小节中的  F \[ i \] \[ v \] F\[i\]\[v\] F\[i\]\[v\]。以递减顺序计算  F \[ v \] F\[v\] F\[v\] 的值，就可以得到上一次循环时计算得到的值，即  F \[ i − 1 \] \[ v \] F\[i-1\]\[v\] F\[i−1\]\[v\] 和  F \[ i − 1 \] \[ v − C i \] F\[i-1\]\[v-C\_i\] F\[i−1\]\[v−Ci\]。

**伪代码**如下：  
 F \[ 0 ⋯ V \]    ←    0 f o r    i    ←    1    t o    N f o r    v    ←    V    t o    C i F \[ v \]    ←    m a x \{ F \[ v \] , F \[ v − C i \] + W i \} \\begin\{aligned\} & F\[0\\cdots V\]\\;\\leftarrow\\;0 \\\\ & for \\; i \\;\\leftarrow\\; 1 \\; to \\; N \\\\ & \\qquad for \\; v \\;\\leftarrow\\; V \\; to \\; C\_i \\\\ & \\qquad\\qquad F\[v\] \\;\\leftarrow\\; max\\\{F\[v\],F\[v-C\_i\]+W\_i\\\} \\end\{aligned\} F\[0⋯V\]←0fori←1toNforv←VtoCiF\[v\]←max\{ F\[v\],F\[v−Ci\]\+Wi\}其中的  F \[ v \]    ←    m a x \{ F \[ v \] , F \[ v − C i \] + W i \} F\[v\] \\;\\leftarrow\\; max\\\{F\[v\],F\[v-C\_i\]+W\_i\\\} F\[v\]←max\{ F\[v\],F\[v−Ci\]\+Wi\} 就对应于我们原来的转移方程。

事实上，使用一维数组解 01 背包的程序在后面会被多次用到，所以这里抽象出一个处理一件 01 背包中的物品过程，以后的代码中直接调用不加说明。01 背包问题的伪代码就可以这样写：  
 d e f    Z e r o O n e P a c k ( F , C , W ) f o r    v    ←    V    t o    C F \[ v \]    ←    m a x \{ F \[ v \] , F \[ v − C \] + W \} F \[ 0 ⋯ V \]    ←    0 f o r    i    ←    1    t o    N Z e r o O n e P a c k ( F , C i , W i ) \\begin\{aligned\} & def \\; ZeroOnePack(F, C, W) \\\\ & \\qquad for \\; v \\;\\leftarrow\\; V \\; to \\; C \\\\ & \\qquad\\qquad F\[v\] \\;\\leftarrow\\; max\\\{F\[v\],F\[v-C\]+W\\\} \\\\ & \\\\ & F\[0\\cdots V\] \\;\\leftarrow\\; 0 \\\\ & for \\; i \\;\\leftarrow\\; 1 \\; to \\; N \\\\ & \\qquad ZeroOnePack(F, C\_i, W\_i) \\end\{aligned\} defZeroOnePack(F,C,W)forv←VtoCF\[v\]←max\{ F\[v\],F\[v−C\]\+W\}F\[0⋯V\]←0fori←1toNZeroOnePack(F,Ci,Wi)

### 3.2 代码 ###

**Java代码**如下：

// 01背包问题
        public static int problem(int N, int V, int[] C, int[] W){
        
            int[] dp = new int[V+1];
            for (int i = 1; i <= N; i++) {
        
                ZeroOnePack(dp, C[i-1], W[i-1]);
            }
            return dp[V];
        }
    
        public static void ZeroOnePack(int[] dp, int C, int W) {
        
            for (int i = dp.length-1; i >= C; i--) {
        
                dp[i] = Math.max(dp[i], dp[i-C] + W);
            }
        }

## 四、初始化的细节问题 ##

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

*  如果是第一种问法，要求恰好装满背包，那么在初始化时除了  F \[ 0 \] F\[0\] F\[0\] 为  0 0 0，其它  F \[ 1 ⋯ V \] F\[1\\cdots V \] F\[1⋯V\] 均设为  − ∞ -\\infty −∞，这样就可以保证最终得到的  F \[ V \] F\[V\] F\[V\] 是一种恰好装满背包的最优解。
 *  如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将  F \[ 0 ⋯ V \] F\[0\\cdots V \] F\[0⋯V\] 全部设为  0 0 0。

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

这个小技巧完全可以推广到其它类型的背包问题，后面不再对进行状态转移之前的初始化进行讲解。

## 五、一个常数优化 ##

上面伪代码中的  
 f o r    i    ←    1    t o    N f o r    v    ←    V    t o    C i \\begin\{aligned\} & for \\; i \\;\\leftarrow\\; 1 \\; to \\; N \\\\ & \\qquad for \\; v \\;\\leftarrow\\; V \\; to \\; C\_i \\\\ \\end\{aligned\} fori←1toNforv←VtoCi中第二重循环的下限可以改进。它可以被优化为  
 f o r    i    ←    1    t o    N f o r    v    ←    V    t o    m a x \{ V − Σ i N W i , C i \} \\begin\{aligned\} & for \\; i \\;\\leftarrow\\; 1 \\; to \\; N \\\\ & \\qquad for \\; v \\;\\leftarrow\\; V \\; to \\; max\\\{V-\\Sigma\_i^N W\_i, C\_i\\\} \\\\ \\end\{aligned\} fori←1toNforv←Vtomax\{ V−ΣiNWi,Ci\}这个优化之所以成立的原因请读者自己思考。（提示：使用二维的转移方程思考较易。）

## 六、小结 ##

01 背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想。另外，别的类型的背包问题往往也可以转换成 01 背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及空间复杂度怎样被优化。