02-26 14:14 南昌航空大学 Java 发布于江西
关注
动态规划：分割等和子集（01背包问题）
//本题目可以转换为:容量为num/2的背包,这n个物品的体积和价值都相等,求dp[sum/2]是否等于sum/2
class Solution {
public boolean canPartition(int[] nums) {
int target=0;
for (int num : nums) {
target+=num;
}
if (target%2!=0) return false;
target/=2;
int []dp=new int[target+1];
Arrays.fill(dp,0);
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]);
}
}
if (dp[target]==target) return true;
else return false;
}
}
//当dp[target]=target,说明在sum/2的容量下,里面的数字之和刚好也为sum/2
//01背包不仅能解决最大价值问题,还可以解决能否装满背包的问题
class Solution {
public boolean canPartition(int[] nums) {
int target=0;
for (int num : nums) {
target+=num;
}
if (target%2!=0) return false;
target/=2;
int []dp=new int[target+1];
Arrays.fill(dp,0);
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]);
}
}
if (dp[target]==target) return true;
else return false;
}
}
//当dp[target]=target,说明在sum/2的容量下,里面的数字之和刚好也为sum/2
//01背包不仅能解决最大价值问题,还可以解决能否装满背包的问题
全部评论
相关推荐
查看20道真题和解析 点赞 评论 收藏
分享