⭐️前面的动态话⭐️
本篇文章将介绍算法专题之动态规划中的背包问题,更准确的规划说是背包问题中最简单的一种类型,即0-1背包问题,包问就是题详给你一定容量的背包和若干物品,每种物品只能选一次,解分告诉你每件物品的析原价值和体积,求背包里面物品的动态最大总价值。
📒博客主页:未见花闻的规划博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创,CSDN首发!包问
📆首发时间:🌴2022年5月8日🌴
✉️坚持和努力一定能换来诗与远方!题详
💭推荐书籍:📚《算法》,解分📚《漫画算法》
💬参考在线编程网站:🌐牛客网🌐力扣
博主的析原码云gitee,平常博主写的动态程序代码都在里面。
博主的规划github,平常博主写的包问程序代码都在里面。
🍭作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!
📌导航小助手📌
- ⭐️0-1背包问题⭐️
- 🔐题目详情
- 💡解题思路
- 🔓朴素0-1背包通解
- ✨优化方案
- 📝练习:分割等和子集
- 🔑习题解答
- ✂️分割等和子集:从最多不超过到恰好
背包问题:泛指一类「给定价值与成本」,同时「限定决策规则」,在这样的条件下,如何实现价值最大化的问题。
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]
,我们可以选择该物品也可以不选择该物品,如果不选择该物品则 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j]=dp[i-1][j] dp[i][j]=dp[i−1][j],如果选择该物品有两种情况:
- 背包剩余空间不够了,那么此时就无法选择该物品, d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j]=dp[i-1][j] dp[i][j]=dp[i−1][j]。
- 背包剩余空间充足,那么此时的物品总价值为 d p [ i ] [ j ] = d p [ i − 1 ] [ j − v [ i ] ] + w [ i ] dp[i][j]=dp[i-1][j-v[i]] + w[i] dp[i][j]=dp[i−1][j−v[i]]+w[i]。
综上,转移方程为 d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − v [ i ] ] + w [ i ] ) dp[i][j]=max(dp[i-1][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]; }
✨优化方案
滚动数组优化:
我们根据状态转移方程 d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − v [ i ] ] + w [ i ] ) dp[i][j]=max(dp[i-1][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])不难发现,计算某一行的值只与前一行有关,所以假设物品总件数为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]; }
一维数组优化:
我们再来看一眼状态转移方程: d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − v [ i ] ] + w [ i ] ) dp[i][j]=max(dp[i-1][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]),我们发现求第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
。
那这个问题可以分为两步:
- 第一步,求元素和在不超过
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]
,我们可以选择该物品也可以不选择该物品,如果不选择该物品则 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j]=dp[i-1][j] dp[i][j]=dp[i−1][j],如果选择该物品有两种情况:
- 背包剩余空间不够了,那么此时就无法选择该物品, d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j]=dp[i-1][j] dp[i][j]=dp[i−1][j]。
- 背包剩余空间充足,那么此时的物品总价值为 d p [ i ] [ j ] = d p [ i − 1 ] [ j − n u m s [ i ] ] + n u m s [ i ] dp[i][j]=dp[i-1][j-nums[i]] + nums[i] dp[i][j]=dp[i−1][j−nums[i]]+nums[i]。
综上,状态转移方程为 d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − n u m s [ i ] ] + n u m s [ i ] ) dp[i][j]=max(dp[i-1][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
的情况下,价值与容量是一比一的关系求最大价值。 - 定义状态,确定初始转态。
- 根据状态转移方程 d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − n u m s [ i ] ] + n u m s [ i ] ) dp[i][j]=max(dp[i-1][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/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
的最大元素和,然后再进行判断,这个过程相当于【间接求解】,其实可以不经过求解最大元素和这一个过程,可以直接进行求解。也就是将求【最大价值问题】变为求【是否等于特定价值问题】。
状态定义:
最大价值问题的状态定义:
d p [ i ] [ j ] dp[i][j] dp[i][j]表示在前 i i i个唯一物品中选择,总容量不超过 j j j的最大价值。
那么是否等于特定价值的定义为:
d p [ i ] [ j ] dp[i][j] dp[i][j]表示在前 i i i个唯一物品中选择,总价值是否等于 j j j,类型为 b o o l e a n boolean boolean。
初始状态确定:
当只有 n u m s [ 0 ] nums[0] nums[0]一个物品时, d p [ 0 ] [ j ] dp[0][j] dp[0][j]的状态到底是什么呢?只能说确定不了,因为根本就不知道 n u m s [ 0 ] nums[0] nums[0]是否等于 j j j,所以这个状态不能取为初始状态。
在这里有一个技巧,就是我们可以考虑没有物品可选择的情况作为初始状态,因为没有物品选择,所以得到的价值一定是 0 0 0,那么 d p [ 0 ] [ 0 ] = t r u e , d p [ 0 ] [ j ] = f a l s e , j >0 dp[0][0]=true, dp[0][j]=false, j>0 dp[0][0]=true,dp[0][j]=false,j>0,由于无物品状态占了一行,所以我们动归数组需要多建一行,并且从 1 1 1开始表示有物品的状态,那么第 i i i件物品对应的是数组中下标为 i − 1 i-1 i−1的物品。
状态转移方程:
对于第i
件物品,它的价值为nums[i-1]
。
如果我们不选择它,则 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j]=dp[i-1][j] dp[i][j]=dp[i−1][j]。
如果我们选择它,如果 j >= n u m s [ i ] j>=nums[i] j>=nums[i],则 d p [ i ] [ j ] = d p [ i − 1 ] [ j − n u m s [ i − 1 ] ] dp[i][j]=dp[i-1][j-nums[i-1]] dp[i][j]=dp[i−1][j−nums[i−1]],否则为 f a l s e false false。
只要上述两种情况有一种满足总价值恰好等于目标价值,则 d p [ i ] [ j ] = t r u e dp[i][j]=true dp[i][j]=true,所以状态转移方程为:
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] ∣ ∣ d p [ i − 1 ] [ j − n u m s [ i − 1 ] ] dp[i][j]=dp[i-1][j]\ ||\ dp[i-1][j-nums[i-1]] 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]; }}
类似题:
求正数数组的最小不可组成和
🌱参考资料:
宫水三叶背包问题