对于0/1背包问题,是一类比较经典的问题,主要就是对于物品是否放入背包的一个考量,从难易程度上来说,个人感觉二维的比一维的更好理解.
对于二维,整个dp数组的推倒过程就是从左上到右下的一个过程,那么是具体怎么推倒的的:
以这个为例:dp[i][j]表示的含义是对于第i个物品,在已经占用重量为j的情况下所获得的最大价值.
对于第i个物品,操作就很明显了,因为是0/1背包,那么只有放和不放两种,放的话,就要dp[i-1][j-weight[i]] + value;不放,那就从上面的同层直接拿下来,也就是dp[i-1][j]当中,所以比较好理解.
例题如下:
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
class Solution {
public boolean canPartition(int[] nums) {
int sum_ = Arrays.stream(nums).sum();
if(sum_ % 2 != 0){
return false;
}
int sum_2 = sum_ / 2 ;
System.out.println(sum_2);
//容量是sum_,重量是nums[i]
int[][] dp = new int [nums.length][sum_2 + 1];
for(int i = 0; i < sum_2; i++){
if(i < nums[0]){
dp[0][i] = 0;
}else{
dp[0][i] = nums[0];
}
}
for(int i = 1; i < nums.length; i++){
for(int j = 1; j <= sum_2; j++){
if(j < nums[i]){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-nums[i]] + nums[i]);
}
}
}
// for(int i = 0; i < nums.length; i++){
// for(int j = 0; j <= sum_2; j++){
// System.out.print(dp[i][j]);
// System.out.print(" ");
// }
// System.out.println();
// }
// System.out.print(dp[nums.length - 1][sum_2 - 1]);
return dp[nums.length - 1][sum_2 ] == sum_2;
}
}思路如下,将物品视位重量和价值相同的特殊物品,向背包中装填,如果恰好能装够一半的重量,那么则是符合要求的.难点在于:对于dp[i][j]大小的定义,j代表包的容量,那么应该定义为物品总重量的一半+1,为什么加1?因为物品的重量是从1开始的,也就是说没有重量是0的物品,如果总的重量不加1,那么无法遍历到最后.对于物品数量也就是行数,则没有什么特殊要求.
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/88864.html
