题目链接(opens new window) 题目难易:中等 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1:
示例 2:
提示:
对于这种类型的题 我们一上来首先想到的肯定不是动归 ,而使回溯,回溯解决切割问题。但是这道题相对于也是可以使用dp去解决的
这道题 他求解的是是否可以分割成两个相等的子集 ,既然想要相同, 那么想要相同,那sum肯定不能是基数 ,如果是奇数 那么就不可能平分 ,所以我们可以先进行判断 ,排除一些不可能的结果。
确定dp数组 含义 以及下标的含义
首先对比背包问题使用dp的的方法
所以说对于本体来讲 ,我们使用的是 数值 那么它的重量 和 价值是相同的
我们所求的最大重量 : 就是 子集中的元素相加最大
容量 : 给定的数组中的所有元素之和 / 2得到的结果 + 1 就是最大容量‘【加一是因为整除他会向下取整】
容量最大值 : 【注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200】 那么就是 (100 * 200 )/2
确定dp公式
我们要求的是dp[j] 也就是容量为 j 的背包的最大重量
那么也就是对于每一个 dp[j] 我们都要比较大小 ,然后返回最大的即可
本题,相当于背包里放入数值,那么物品i的重量是nums[i],其价值也是nums[i]。
dp[j] = Math.max(dp[j] , dp[j - nums[i]] + nums[i])
dp的初始化 及大小
对于dp数组而言 , 它的初始化 是根据题意来进行写的, 我们这里就是初始化为 0
dp数组的大小 也就是背包的所能承受的最大重量
容量 : 给定的数组中的所有元素之和 / 2得到的结果 + 1 就是最大容量‘【加一是因为整除他会向下取整】
容量最大值 : 【注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200】 那么就是 (100 * 200 )/2
遍历顺序
同样的 和背包问题一样, 我们这里需要两层遍历
第一层遍历数值
第二层遍历背包
// 开始 01背包
for(int i = 0; i < nums.length; i++) {
for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入,所以从大到小遍历
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
我们不能只简单的实现dp数组 ,根据题目要求 ,我们需要判断 该数组能否完成分割 ,也就是dp数组的最大重量是否等于背包的最大重量
所以需要进行判断
if(dp[target] == target)
return true;
else
return false;
class Solution {
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0) return false;
int n = nums.length;
int sum = 0;
for(int num : nums) {
sum += num;
}
//总和为奇数,不能平分
if(sum % 2 != 0) return false;
int target = sum / 2;
int[] dp = new int[target + 1];
for(int i = 0; i < n; i++) {
for(int j = target; j >= nums[i]; j--) {
//物品 i 的重量是 nums[i],其价值也是 nums[i]
dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
}
}
return dp[target] == target;
}
}
题目链接(opens new window) 题目难度:中等 有一堆石头,每块石头的重量都是正整数。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下: 最后,最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下,就返回 0。 示例:
解释:
提示:
本题的目的是让我们找到碰撞之后 ,重量最小的石头的重量。 同样的 , 我们可以将其换位思考变化为背包问题
关键点:
碰撞之后的重量最小的石头 ,那么就相当于 将两个大小相似的石头进行碰撞 ,到最后剩下的 那么一定是重量最小的石头 ,因为我们找的是重量相近的两个石头碰撞
那么问题的关键就是怎么寻找重量相近的石头 ,答案很简单
先对数组进行求和sum ,然后将 sum/ 2 ,得到一个结果target ,那么另一个值就是 (sum - sum/2) —>(sum -target)
那么我们所需要的最小值就一定是 target - (sum - target) 的绝对值 ,为什么取绝对值 ? 因为我们不知道 target 和 sum-target到底哪个大
就刚刚我们的思路而言 ,本题的思路 和 实现 上一题 基本上是如出一辙 。
dp[j] 表示 : 容量为 j 的背包 ,放置的物品的最大重量为dp[j]
换位思考到本题即可
dp[j] = Math.max(dp[j] , dp[j - nums[i]] + nums[i])
这里我们全部初始化为0 即可
大小 :也就是数组中的所有元素之和 / 2得到的结果 + 1 就是最大容量【加一是因为整除他会向下取整】
和前面的题一样。 如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历
相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target] —> sum - 2 * dp[target]
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int i : stones) {
sum += i;
}
int target = sum >> 1;
//初始化dp数组
int[] dp = new int[target + 1];
for (int i = 0; i < stones.length; i++) {
//采用倒序
for (int j = target; j >= stones[i]; j--) {
//两种情况,要么放,要么不放
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - 2 * dp[target];
}
}