⭐️前面的话⭐️

本篇文章将介绍算法专题之动态规划中的背包问题，更准确的说是背包问题中最简单的一种类型，即0-1背包问题，就是给你一定容量的背包和若干物品，每种物品只能选一次，告诉你每件物品的价值和体积，求背包里面物品的最大总价值。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2022年5月8日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《漫画算法》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

---

---

背包问题：泛指一类「给定价值与成本」，同时「限定决策规则」，在这样的条件下，如何实现价值最大化的问题。
0-1背包：「01背包」是指给定物品价值与体积（对应了「给定价值与成本」），在规定容量下（对应了「限定决策规则」）如何使得所选物品的总价值最大。 （来自宫水三叶）

---

⭐️0-1背包问题⭐️

🔐题目详情

有 N 件物品和一个容量是 V 的背包。每件物品有且只有一件。

第 i 件物品的体积是v[i] ，价值是w[i] 。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

示例 1：

输入: N = 3, V = 4, v = [4,2,3], w = [4,2,3]
输出: 4
解释: 只选第一件物品，可使价值最大。
1
2
3

示例 2：

输入: N = 3, V = 5, v = [4,2,3], w = [4,2,3]
输出: 5
解释: 不选第一件物品，选择第二件和第三件物品，可使价值最大。
1
2
3

💡解题思路

分析：

这道题目的意思是给你一堆物品，每种物品只有一件，然后就是在这些物品中选一部分放入背包，在不超过背包容量的情况下，求背包里面物品的最大总价值。

🔓朴素0-1背包通解

状态定义：

本质上就是从i个物品中选择一定数量的物品在一定空间限制的前提下，求这些物品的最大总价值，我们可以定义一个二维数组dp[i][j]，这个数组的值就表示从前i件物品进行选择，在不超过容量j的前提下所满足最大的物品总价值。（注：此处的第i件物品对应与数组下标i）

确定初始状态：

当只有一个物品时，如果该物品的体积v不大于背包容量j，则初始值dp[0][j]=v，否则dp[0][j]=0。

状态转移方程：

对于第i件物品，设它的所占容量为v[i]，价值为w[i]，我们可以选择该物品也可以不选择该物品，如果不选择该物品则$dp[i][j]=dp[i-1][j]$，如果选择该物品有两种情况：

• 背包剩余空间不够了，那么此时就无法选择该物品，$dp[i][j]=dp[i-1][j]$。
• 背包剩余空间充足，那么此时的物品总价值为$dp[i][j]=dp[i-1][j-v[i]]+w[i]$。

综上，转移方程为$dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])$。

实现代码：

    /**
     *
     * @param N 物品数
     * @param C 背包容量
     * @param v 每件的体积
     * @param w 每件物品的价值
     * @return 最大价值
     */
    public int zoKnapsack(int N, int C, int[] v, int[] w) {
        //0-1背包朴素
        int[][] dp = new int[N][C+1];
        //初始化
        for (int j = 0; j <= C; j++) {
            dp[0][j] = j >= v[0] ? w[0] : 0;
        }

        //处理剩余元素
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= C; j++) {
                //不选
                int x = dp[i-1][j];
                //选
                int y = j >= v[i] ? dp[i-1][j-v[i]] + w[i] : 0;
                //取两者中的最大值
                dp[i][j] = Math.max(x, y);
            }
        }
        return dp[N-1][C];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

✨优化方案

滚动数组优化：

我们根据状态转移方程$dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])$不难发现，计算某一行的值只与前一行有关，所以假设物品总件数为n，背包总空间大小为c，原本需要使用n行c列的数组，可以优化为2行c列的二维数组，这两行按照偶奇的顺序交替使用。

其中，在进行奇偶行转换时，可以使用i%2或者i&1进行下标替换，因为&运算符比%运算符稳定，所以更推荐i&1。

实现代码：

    public int zoKnapsackPlus(int N, int C, int[] v, int[] w) {
        //0-1背包滚动数组优化
        int[][] dp = new int[2][C+1];
        //初始化
        for (int j = 0; j <= C; j++) {
            dp[0][j] = j >= v[0] ? w[0] : 0;
        }

        //处理剩余元素
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= C; j++) {
                //不选
                int x = dp[(i-1) & 1][j];
                //选
                int y = j >= v[i] ? dp[(i-1) & 1][j-v[i]] + w[i] : 0;
                //取两者中的最大值
                dp[i&1][j] = Math.max(x, y);
            }
        }
        return dp[(N-1) & 1][C];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

一维数组优化：

我们再来看一眼状态转移方程：$dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])$，我们发现求第i行第j列格子的值时，只与i-1行的格子有关，并且明确依赖第j列和第j-v[i]列，相当于新的第j列数据只与旧的第j列和旧的第j-v[i]列有关，所以我们可以对二维数组进行优化，可以优化成一维数组，即仅保留 背包容量维度。

优化后物品的最大价值为dp[j]，新的dp[j]与旧的dp[j]与旧的dp[j-v[i]]有关，即计算新一轮dp[j]时，dp[j-v[i]]必须是没有更新的值，从上图可知dp[j-v[i]]的位置在dp[j]位置的前面，所以在更新新一轮的最大总价值时，需先更新dp[j]的值再更新dp[j-v[i]]的值，所以j的遍历顺序为从后往前，同时为了保证j>=v[i]，遍历的最小值为v[i]。

实现代码：

    public int zoKnapsackOnePlus(int N, int C, int[] v, int[] w) {
        //0-1背包滚动数组优化
        int[] dp = new int[C+1];
        //初始化
        for (int j = 0; j <= C; j++) {
            dp[j] = j >= v[0] ? w[0] : 0;
        }

        //处理剩余元素
        for (int i = 1; i < N; i++) {
            for (int j = C; j >= v[i]; j--) {
                //不选
                int x = dp[j];
                //选
                int y = dp[j-v[i]] + w[i];
                //取两者中的最大值
                dp[j] = Math.max(x, y);
            }
        }
        return dp[C];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

📝练习：分割等和子集

题目：416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
1
2
3

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
1
2
3

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

🔑习题解答

分析：
本题的意思是给你一个只含有正整数的数组nums，将此数组分成两个子集，并且这两个子集的元素和是相等的，那就相当于两个子集的元素和都等于原数组nums元素和的一半，现在我们不妨记原数组nums的元素和为sum，那么如果sum为奇数，怎么分割数组都分不出两个元素和相等的子集，此时直接返回false即可，如果sum为偶数，是有可能能分出两个元素和相等的子集的，换个角度想想，如果其中一个子集能够凑出sum/2，那另外一个子集自然而然也能凑出sum/2，所以这个时候这个问题就转换成：从数组中选择元素，每个元素只能被选择一次，判断被选出的这些元素的和是否等于sum/2。

那这个问题可以分为两步：

• 第一步，求元素和在不超过sum/2情况下的最大元素和。
• 第二步，判断所求的元素和是否等于sum/2。

对于其中的第一步，其实完完全全就是 0-1背包问题，即背包的最大容量为c=sum/2，题目给你的数组nums，就是物品所对应的容量，物品的容量与价值是一比一的关系，在上述限制的条件下求背包中物品的最大价值。

状态定义：

我们可以定义一个二维数组dp[i][j]，这个数组的值就表示从前i件物品进行选择，在不超过容量j的前提下所满足最大的物品总价值。（注：此处的第i件物品对应与数组下标i）

确定初始状态的值：

当只有一个物品时，如果该物品的体积v不大于背包容量j，则初始值dp[0][j]=v，否则dp[0][j]=0。

状态转移方程：

依题意，对于第i件物品，它的所占容量为nums[i]，价值也为nums[i]，我们可以选择该物品也可以不选择该物品，如果不选择该物品则$dp[i][j]=dp[i-1][j]$，如果选择该物品有两种情况：

• 背包剩余空间不够了，那么此时就无法选择该物品，$dp[i][j]=dp[i-1][j]$。
• 背包剩余空间充足，那么此时的物品总价值为$dp[i][j]=dp[i-1][j-nums[i]]+nums[i]$。

综上，状态转移方程为$dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i])$。

总体解题流程：

• 求数组的元素和sum，如果sum为偶数，则进行下一步，否则返回false。
• 转换为0-1背包，在最大容量为sum/2的情况下，价值与容量是一比一的关系求最大价值。
• 定义状态，确定初始转态。
• 根据状态转移方程$dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i])$计算最大元素和。
• 判断最大元素和是否与sum/2相等。

转换为0-1背包实现代码：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        // 1.求和
        for (int x : nums) {
            sum += x;
        }
        // 2.如果和为奇数，那一定不能分割
        if ((sum & 1) == 1) {
            return false;
        }
        // 3.转换为0-1背包
        int n = nums.length;
        int c = sum / 2;
        int[][] dp = new int[n][c+1];

        for (int j = 0; j <= c; j++) {
            dp[0][j] = j >= nums[0] ? nums[0] : 0;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= c; j++) {
                int pre = dp[i-1][j];

                int cur = j >= nums[i] ? dp[i-1][j-nums[i]] + nums[i] : pre;
                dp[i][j] = Math.max(pre, cur);
            }
        }
        // 4.判断最终背包的价值是否等于sum/2，如果相等表示可以分割
        return dp[n-1][c] == c;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

转换为0-1背包，滚动数组优化实现代码：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        // 1.求和
        for (int x : nums) {
            sum += x;
        }
        // 2.如果和为奇数，那一定不能分割
        if ((sum & 1) == 1) {
            return false;
        }
        // 3.转换为0-1背包
        int n = nums.length;
        int c = sum / 2;
        int[][] dp = new int[2][c+1];

        for (int j = 0; j <= c; j++) {
            dp[0][j] = j >= nums[0] ? nums[0] : 0;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= c; j++) {
                int index = (i-1) & 1;
                int pre = dp[index][j];

                int cur = j >= nums[i] ? dp[index][j-nums[i]] + nums[i] : pre;
                dp[i&1][j] = Math.max(pre, cur);
            }
        }
        // 4.判断最终背包的价值是否等于sum/2，如果相等表示可以分割
        return dp[(n-1)&1][c] == c;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

优化为一维数组实现代码：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        // 1.求和
        for (int x : nums) {
            sum += x;
        }
        // 2.如果和为奇数，那一定不能分割
        if ((sum & 1) == 1) {
            return false;
        }
        // 3.转换为0-1背包
        int n = nums.length;
        int c = sum / 2;
        //我们发现dp[i][j]只与dp[i-1][j]和dp[i-1][j-nums[i]]有关，我们可以把剩余空间数从0-c遍历改为c-0遍历,只保留剩余空间维度
        int[] dp = new int[c+1];

        for (int i = 0; i < n; i++) {
            for (int j = c; j >= nums[i]; j--) {
                int pre = dp[j];
                int cur = dp[j-nums[i]] + nums[i];
                dp[j] = Math.max(pre, cur);
            }
        }
        // 4.判断最终背包的价值是否等于sum/2，如果相等表示可以分割
        return dp[c] == c;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

✂️分割等和子集：从最多不超过到恰好

上面我们在分析【分割等和子集】时，问题可以转化为：从数组中选择元素，每个元素只能被选择一次，判断被选出的这些元素的和是否等于sum/2。

前面我们的做法是先求出这个不超过sum/2的最大元素和，然后再进行判断，这个过程相当于【间接求解】，其实可以不经过求解最大元素和这一个过程，可以直接进行求解。也就是将求【最大价值问题】变为求【是否等于特定价值问题】。

状态定义：

最大价值问题的状态定义：
$dp[i][j]$表示在前$i$个唯一物品中选择，总容量不超过$j$的最大价值。

那么是否等于特定价值的定义为：
$dp[i][j]$表示在前$i$个唯一物品中选择，总价值是否等于$j$，类型为$boolean$。

初始状态确定：
当只有$nums[0]$一个物品时，$dp[0][j]$的状态到底是什么呢？只能说确定不了，因为根本就不知道$nums[0]$是否等于$j$，所以这个状态不能取为初始状态。

在这里有一个技巧，就是我们可以考虑没有物品可选择的情况作为初始状态，因为没有物品选择，所以得到的价值一定是$0$，那么$dp[0][0]=true,dp[0][j]=false,j>0$，由于无物品状态占了一行，所以我们动归数组需要多建一行，并且从$1$开始表示有物品的状态，那么第$i$件物品对应的是数组中下标为$i-1$的物品。

状态转移方程：
对于第i件物品，它的价值为nums[i-1]。
如果我们不选择它，则$dp[i][j]=dp[i-1][j]$。
如果我们选择它，如果$j>=nums[i]$，则$dp[i][j]=dp[i-1][j-nums[i-1]]$，否则为$false$。

只要上述两种情况有一种满足总价值恰好等于目标价值，则$dp[i][j]=true$，所以状态转移方程为：
$$dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]]$$

实现代码：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        // 1.求和
        for (int x : nums) {
            sum += x;
        }
        // 2.如果和为奇数，那一定不能分割
        if ((sum & 1) == 1) {
            return false;
        }
        // 3.转换为0-1背包
        int n = nums.length;
        int c = sum / 2;
        boolean[][] dp = new boolean[n+1][c+1];
        // 4.初始化
        dp[0][0] = true;

        // 5.处理剩余状态
        for (int i = 1; i <= n; i++) {
            int val = nums[i-1];
            for (int j = 0;  j <= c; j++) {
                //不选择
                boolean no = dp[i-1][j];
                //选择
                boolean yes = j >= val ? dp[i-1][j - val] : false;
                dp[i][j] = no || yes;
            }
        }
        return dp[n][c];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

滚动数组优化：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        // 1.求和
        for (int x : nums) {
            sum += x;
        }
        // 2.如果和为奇数，那一定不能分割
        if ((sum & 1) == 1) {
            return false;
        }
        // 3.转换为0-1背包
        int n = nums.length;
        int c = sum / 2;
        boolean[][] dp = new boolean[2][c+1];
        // 4.初始化
        dp[0][0] = true;

        // 5.处理剩余状态
        for (int i = 1; i <= n; i++) {
            int val = nums[i-1];
            for (int j = 0;  j <= c; j++) {
                //不选择
                int index = (i-1) & 1;
                boolean no = dp[index][j];
                //选择
                boolean yes = j >= val ? dp[index][j - val] : false;
                dp[i&1][j] = no || yes;
            }
        }
        return dp[n&1][c];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

一维数组优化：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        // 1.求和
        for (int x : nums) {
            sum += x;
        }
        // 2.如果和为奇数，那一定不能分割
        if ((sum & 1) == 1) {
            return false;
        }
        // 3.转换为0-1背包
        int n = nums.length;
        int c = sum / 2;
        boolean[] dp = new boolean[c+1];
        // 4.初始化
        dp[0] = true;

        // 5.处理剩余状态
        for (int i = 1; i <= n; i++) {
            int val = nums[i-1];
            for (int j = c;  j >= val; j--) {
                dp[j] =dp[j] || dp[j - val];
            }
        }
        return dp[c];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

---

类似题：
求正数数组的最小不可组成和

🌱参考资料：

宫水三叶背包问题

觉得文章写得不错的老铁们，点赞评论关注走一波！谢谢啦！