一篇文章吃透背包问题！！！【动态规划】

Myth丶恋晨 2024-03-25 10:19 62阅读 0赞

#### 背包问题 ####

*  什么是背包问题？
 *  背包问题分类:
 *   *  0 - 1背包
     *   *  解题思路：
         *  万能统一代码：(Java、C++)
         *  空间优化
     *  完全背包
     *   *  解题思路：
         *  万能统一代码：(Java、C++)
         *  空间优化
 *  无法使用贪心算法的解释
 *  LeetCode题目 —— 实战 ！！！：

## 什么是背包问题？ ##

*  简单来说就是：一个小偷背了一个背包潜进了金店，包就那么大，他如果保证他背出来所有物品加起来的**价值最大**。
 *  规范描述就是：有一个容量为 `W` 的背包，要用这个背包装下物品的**价值最大**，这些物品有两个属性：体积 `w` 和价值 `v`。

![在这里插入图片描述][6b24576641394db8b0b1d9a375cab10e.png]

## 背包问题分类: ##

最常见的背包问题有**0-1背包**，**完全背包**，**多重背包**，**分组背包**这四种：

*  按照每个**物品的数量**分类。
 *  其中最重要的是 **0 - 1背包** 和 **完全背包** 。

![在这里插入图片描述][3fa2c617d30340af80b62a1555a294b4.png]

### 0 - 1背包 ###

> **问题描述**：一个最多能背体积为 `W` 的**背包** 和 `n` 件**物品**。第 `i` 件物品的体积是 `weight[i]` ，价值是 `value[i]` 。每件物品只能用一次，求解将哪些物品装入背包里物品**价值总和最大**。

#### 解题思路： ####

定义一个二维数组 `dp` 存储最大价值，其中 `dp[i][j]` 表示前 `i` 件物品体积不超过 `j` 的情况下能达到的最大价值。

设第 `i` 件物品体积为 `w[i]`，价值为 `v[i]`，根据第 `i` 件物品 **是否添加** 到背包中，可以分两种情况讨论：

1.  第 `i` 件物品 **没添加** 到背包，总体积不超过 `j` 的前 `i` 件物品的最大价值就是总体积不超过 `j` 的前 `i -1` 件物品的最大价值，`dp[i][j] = dp[i-1][j]`。
2.  第 `i` 件物品 **添加** 到背包中，`dp[i][j] = dp[i-1][j-w[i]] + v[i]`。

![在这里插入图片描述][98e1ea5e63e9469c8d6aba41a65db727.jpeg]

第 `i` 件物品可添加也可以不添加，取决于哪种情况下**最大价值更大**。因此，0 -1 背包的**状态转移公式**为：  
 d p \[ i \] \[ j \] = max ⁡ ( d p \[ i − 1 \] \[ j \] , d p \[ i − 1 \] \[ j − w \[ i \] \] + v \[ i \] ) d p\[i\]\[j\]=\\max (dp\[i-1\]\[j\], dp\[i-1\]\[j-w\[i\]\]+v\[i\]) dp\[i\]\[j\]=max(dp\[i−1\]\[j\],dp\[i−1\]\[j−w\[i\]\]\+v\[i\])

#### 万能统一代码：(Java、C++) ####

**Java:**

// W 为背包总体积
    // N 为物品数量
    // weights 数组存储 N 个物品的重量
    // values 数组存储 N 个物品的价值
    public int knapsack(int W, int N, int[] weights, int[] values) {
        
        int[][] dp = new int[N + 1][W + 1];
        for (int i = 1; i <= N; i++) {
        
            for (int j = 1; j <= W; j++) {
        
                if (j >= weights[i - 1]) {
        
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                } else {
        
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[N][W];
    }

**C++ :**

// W 为背包总体积
    // N 为物品数量
    // weights 数组存储 N 个物品的重量
    // values 数组存储 N 个物品的价值
    int knapsack(int W, int N, vector<int> weights, vector<int> values) {
        
        vector<vector<int>> dp(N + 1, vector<int>(W + 1));
        for (int i = 1; i <= N; i++) {
        
            for (int j = 1; j <= W; j++) {
        
                if (j >= weights[i - 1]) {
        
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                } else {
        
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[N][W];
    }

#### 空间优化 ####

在程序实现时可以对 0 - 1 背包做优化。观察状态转移方程可以知道，前 `i` 件物品的状态仅与前 `i - 1` 件物品的状态有关，因此可以将 `dp` 定义为**一维数组**，其中 `dp[j]` 既可以表示 `dp[i-1][j]` 也可以表示 `dp[i][j]`。此时，  
 d p \[ j \] = max ⁡ ( d p \[ j \] , d p \[ j − w \[ i \] \] + v \[ i \] ) d p\[j\]=\\max (dp\[j\], dp\[j-w\[i\]\]+v\[i\]) dp\[j\]=max(dp\[j\],dp\[j−w\[i\]\]\+v\[i\])

因为要使用 `dp[j-w[i]]` 表示 `dp[i-1][j-w[i]]`，因此不能先求 `dp[i][j-w[i]]`，防止将 `dp[i-1][j-w[i]]` 覆盖。

也就是说要先计算 `dp[i][j]` 再计算 `dp[i][j-w[i]]`，在程序实现时需要按 **倒序** 来循环求解。  
**Java:**

public int knapsack(int W, int N, int[] weights, int[] values) {
        
        int[] dp = new int[W + 1];
        for (int i = 1; i <= N; i++) {
        
            for (int j = W; j >= 1; j--) {
        
                if (j >= weights[i - 1]) {
        
                    dp[j] = Math.max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
                }
            }
        }
        return dp[W];
    }

**C++:**

int knapsack(int W, int N, vector<int> weights, vector<int> values) {
        
        vector<int> dp(W + 1);
        for (int i = 1; i <= N; i++) {
        
            for (int j = W; j >= 1; j--) {
        
                if (j >= weights[i - 1]) {
        
                    dp[j] = Math.max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
                }
            }
        }
        return dp[W];
    }

### 完全背包 ###

> 与 0 - 1 背包问题相似，但在完全背包问题中，**物品的数量是无限的**，可以选择任意多个相同的物品放入背包。

#### 解题思路： ####

和 0 - 1 背包类似，我们可以定义一个二维数组 `dp`，其中 `dp[i][j]` 表示在前 `i` 个物品中，背包容量为 `j` 时能够获得的最大价值。

动态规划的**状态转移公式**如下：  
 d p \[ i \] \[ j \] = m a x ( d p \[ i − 1 \] \[ j \] , d p \[ i \] \[ j − w \[ i \] \] + v \[ i \] ) dp\[i\]\[j\] = max(dp\[i-1\]\[j\], dp\[i\]\[j-w\[i\]\] + v\[i\]) dp\[i\]\[j\]=max(dp\[i−1\]\[j\],dp\[i\]\[j−w\[i\]\]\+v\[i\])

*  其中 `w[i]` 表示第 `i` 个物品的重量，`v[i]` 表示第 `i` 个物品的价值。
 *  第一项 `dp[i-1][j]` 表示 **不选择** 第 `i` 个物品;
 *  第二项 `dp[i][j-w[i]] + v[i]` 表示 **选择** 第 `i` 个物品（可能不止一个，和0-1背包相区别！）。

#### 万能统一代码：(Java、C++) ####

**Java:**

// W 为背包总体积
    // N 为物品的种类
    // weights 数组存储 N 个物品的重量
    // values 数组存储 N 个物品的价值
    public int knapsack(int W, int N, int[] weights, int[] values) {
        
        int[][] dp = new int[N + 1][W + 1];
        for (int i = 1; i <= N; i++) {
        
            for (int j = 1; j <= W; j++) {
        
                if (j >= weights[i - 1]) {
        
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weights[i - 1]] + values[i - 1]);
                } else {
        
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[N][W];
    }

**C++ :**

// W 为背包总体积
    // N 为物品的种类
    // weights 数组存储 N 个物品的重量
    // values 数组存储 N 个物品的价值
    int knapsack(int W, int N, vector<int> weights, vector<int> values) {
        
        vector<vector<int>> dp(N + 1, vector<int>(W + 1));
        for (int i = 1; i <= N; i++) {
        
            for (int j = 1; j <= W; j++) {
        
                if (j >= weights[i - 1]) {
        
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weights[i - 1]] + values[i - 1]);
                } else {
        
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[N][W];
    }

#### 空间优化 ####

*  和 0 - 1 背包类似，可以优化空间复杂度为**一维数组**，使用 `dp[j]` 表示背包容量为 `j` 时的最大价值。**状态转移公式**为：  
     d p \[ j \] = m a x ( d p \[ j \] , d p \[ j − w \[ i \] \] + v \[ i \] ) dp\[j\] = max(dp\[j\], dp\[j-w\[i\]\] + v\[i\]) dp\[j\]=max(dp\[j\],dp\[j−w\[i\]\]\+v\[i\])

和0-1背包不同，在程序实现时按 **正序** 来循环求解。

**Java:**

public int knapsack(int W, int N, int[] weights, int[] values) {
        
        int[] dp = new int[W + 1];
        for (int i = 1; i <= N; i++) {
        
           for (int j = 1; j <= W; j++) {
        
                if (weights[i - 1] <= j) {
        
                    dp[j] = Math.max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
                }
            }
        }
        return dp[W];
    }

**C++:**

int knapsack(int W, int N, vector<int> weights, vector<int> values) {
        
        vector<int> dp(W + 1);
        for (int i = 1; i <= N; i++) {
        
           for (int j = 1; j <= W; j++) {
        
                if (weights[i - 1] <= j) {
        
                    dp[j] = max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
                }
            }
        }
        return dp[W];
    }

## 无法使用贪心算法的解释 ##

> 0-1 背包问题无法使用贪心算法来求解，也就是说不能按照先添加性价比最高的物品来达到最优，这是因为这种方式**可能造成背包空间的浪费，从而无法达到最优**。

考虑下面的物品和一个容量为 5 的背包:

*  如果先添加物品 0 再添加物品 1，那么只能存放的价值为 16，浪费了大小为 2 的空间。
 *  最优的方式是存放**物品 1** 和**物品 2**，价值为 22.

![在这里插入图片描述][6726e552152f4f79a2748e163017efb0.png]

> 所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的;  
> **只需记住**：动规是由前一个状态**推导**出来的，而贪心是**局部直接选最优**的。

## LeetCode题目 —— 实战 ！！！： ##

[416. 分割等和子集][416.]  
[494. 目标和][494.]  
[474. 一和零][474.]  
[322. 零钱兑换][322.]  
[518. 零钱兑换 II][518. _ II]  
[139.单词拆分][139.]  
[377. 组合总和 Ⅳ ][377. _ _]  
[1049. 最后一块石头的重量 II ][1049. _ II]

**注：仅供学习参考!**

[6b24576641394db8b0b1d9a375cab10e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a23ba8312a41487282820f7c7cfa3bfc.png
[3fa2c617d30340af80b62a1555a294b4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/cc7949dc89d545fb805f1374f10e6495.png
[98e1ea5e63e9469c8d6aba41a65db727.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8a956cd3ef414a50b5f4213240df9d51.png
[6726e552152f4f79a2748e163017efb0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8763e576619746ed901124dcc669aab3.png
[416.]: https://blog.csdn.net/weixin_43412762/article/details/129474322
[494.]: https://blog.csdn.net/weixin_43412762/article/details/129491376
[474.]: https://blog.csdn.net/weixin_43412762/article/details/129523322
[322.]: https://blog.csdn.net/weixin_43412762/article/details/129551876
[518. _ II]: https://blog.csdn.net/weixin_43412762/article/details/129584109?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22129584109%22%2C%22source%22%3A%22weixin_43412762%22%7D
[139.]: https://blog.csdn.net/weixin_43412762/article/details/129595558
[377. _ _]: https://blog.csdn.net/weixin_43412762/article/details/129621199?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22129621199%22%2C%22source%22%3A%22weixin_43412762%22%7D
[1049. _ II]: https://blog.csdn.net/weixin_43412762/article/details/130730994