💕"2024.3.28小米汽车发布"💕
作者：Lvzi
文章主要内容：算法系列–动态规划–背包问题(2)–01背包拓展题目
大家好,今天为大家带来的是
算法系列--动态规划--背包问题(2)--01背包拓展题目
1.分割等和⼦集
链接:
https://leetcode.cn/problems/partition-equal-subset-sum/
分析:
本题属于01背包问题
从数组中选择一些数据,使其刚好符合某种带限制条件的和,就符合01背包问题的思路
01背包问题就是选择一些物品,实现不超过背包最大容量的最大价值
本题是选择一些数,判断能够实现最大和刚好等于sum/2的情况
还有一个是在分析状态转移方程时,最后一个位置选或者不选也可以用01问题
代码:
class Solution { public boolean canPartition(int[] nums) { int n = nums.length; int sum = 0; for(int x : nums) sum += x;// 求和 if(sum % 2 == 1) return false;// 特判 int N = sum / 2; // 创建dp表 boolean[][] dp = new boolean[n + 1][N + 1]; dp[0][0] = true;// 初始化 for(int i = 1; i <= nums.length; i++) { for(int j = 1; j <= sum / 2; j++) { dp[i][j] = (dp[i - 1][j]) || (j - nums[i - 1] >= 0 && dp[i - 1][j - nums[i - 1]]); } } // 返回值 return dp[nums.length][sum / 2]; } }
空间优化后的代码:
class Solution { public boolean canPartition(int[] nums) { int n = nums.length, sum = 0; for(int x : nums) sum += x; if(sum % 2 == 1) return false; int N = sum / 2; boolean[] dp = new boolean[N + 1]; dp[0] = true; for(int i = 1; i <= n; i++) for(int j = sum / 2; j >= nums[i - 1]; j--) dp[j] = dp[j] || dp[j - nums[i - 1]]; return dp[sum / 2]; } }
2.⽬标和
链接:
https://leetcode.cn/problems/target-sum/
分析:
题目要求是必须用到数组里面的所有数字进行拼接(可正可负),判断可以拼接为target的最大组合数
首先,因为要用到数组中所有的数字,所以可以先把数组总和sum求出,接着我们可以把sum拆分为两部分,一部分是拼接+的数字总和a,另一部分是拼接-的总和b(b是大于0的,这里仅仅只是数字的相加),则可以得出:
a + b == suma - b == target
将两式相加可得:
a == (sum + target) / 2
示意图:
那么本道题就可以转化为在数组中挑选若干个数,使其和等于a的最大组合数,这不就是01背包问题吗!,在一个集合内部挑选若干个物品,在满足某个限制的前提下,实现xxxx
说明:求出a之后还需要判断是否越界,主要有两种不符合条件的情况:
a < 0,因为本题的target可以是负数,所以a可能是负数,但是数组中的数全是大于0的,根部无法凑出一个小于0的数(sum + target) / 2 != 0:当除不尽的时候就代表不存在这样的a,也就无法凑出target,返回0
接下来就是动态规划的思路:
算法系列--动态规划--背包问题(2)--01背包拓展题目（下）
