背包问题：泛指一类「给定价值与成本」，同时「限定决策规则」，在这样的条件下，如何实现价值最大化的问题。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解释: 只选第一件物品，可使价值最大。
复制代码
示例 2：
输入: N = 3, V = 5, v = [4,2,3], w = [4,2,3]输出: 5解释: 不选第一件物品，选择第二件和第三件物品，可使价值最大。
复制代码
💡解题思路
分析：
这道题目的意思是给你一堆物品，每种物品只有一件，然后就是在这些物品中选一部分放入背包，在不超过背包容量的情况下，求背包里面物品的最大总价值。
🔓朴素 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]=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]; }
复制代码
✨优化方案
滚动数组优化：
我们根据状态转移方程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]; }
复制代码
一维数组优化：
我们再来看一眼状态转移方程：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]; }
复制代码
📝练习：分割等和子集
题目：416. 分割等和子集给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]输出：true解释：数组可以分割成 [1, 5, 5] 和 [11] 。
复制代码
示例 2：
输入：nums = [1,2,3,5]输出：false解释：数组不能分割成两个元素和相等的子集。
复制代码
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100
🔑习题解答
分析：本题的意思是给你一个只含有正整数的数组nums，将此数组分成两个子集，并且这两个子集的元素和是相等的，那就相当于两个子集的元素和都等于原数组nums元素和的一半，现在我们不妨记原数组nums的元素和为sum，那么如果sum为奇数，怎么分割数组都分不出两个元素和相等的子集，此时直接返回false即可，如果sum为偶数，是有可能能分出两个元素和相等的子集的，换个角度想想，如果其中一个子集能够凑出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]=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; }}
复制代码
转换为 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;
}}
复制代码
优化为一维数组实现代码：
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; }}
复制代码
✂️分割等和子集：从最多不超过到恰好
上面我们在分析【分割等和子集】时，问题可以转化为：从数组中选择元素，每个元素只能被选择一次，判断被选出的这些元素的和是否等于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]; }}
复制代码
滚动数组优化：
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]; }}
复制代码
一维数组优化：
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]; }}
复制代码
类似题：求正数数组的最小不可组成和
🌱参考资料：
宫水三叶背包问题
评论