代码随想录算法训练营打卡第35天：背包问题

前言

zaccheo打卡代码随想录第35天

---

由于这段时间工作太忙了（加上我的懒病犯了）导致迟打卡了好几天555555.。。。

今天的主要是动态规划中的背包问题，这个真的是蛮难理解的，我把我自己强行按在椅子上半个小时一点一点的看卡哥文章才理解透彻最后又在纸上复盘了一遍

这是卡哥原文章链接：代码随想录

我就直接写我的理解了,dp[i][j]，其中i为物品索引，j为背包重量，dp[i][j]代表的是在加入物品i的时候背包重量为j的最大总价值

当遍历到物品i的时候，取此时背包重量的最大值有两种可能，第一加上物品i，第二不加上物品i，如果不加上物品i背包价值的最大值为dp[i-1][j]

加上物品i此时背包价值的最大值为dp[i-1][j-weight[i]]+value[i]，因为此时背包可以装j的重量，而物品i的重量为weight[i]，则如果加上物品i,背包剩余的重量j-weight[i]，而dp数组又表示代表的是在加入物品i的时候背包重量为j的最大总价值,所以加入物品i时，背包最大价值为dp[i-1][j-weight[i]]+value[i]

最后比较dp[i-1][j]和dp[i-1][j-weight[i]]+value[i]的价值哪个大即为背包的最大总价值

这是二维数组的解法，同时还有一维数组的解法，首先要理解什么是滚动数组，此文章有详细解释：滚动数组（简单说明）_滚动数组思想-CSDN博客

这是卡哥对一维数组解决背包问题的文章：代码随想录

Leetcode416.分割等和子集

这道题可以抽象成背包问题，使用背包问题的思路取解答，二维数组和一维数据解法如下：

class Solution {public boolean canPartition(int[] nums) {Arrays.sort(nums);int sum=0;for(int i=0;i<nums.length;i++){sum+=nums[i];}if(sum%2!=0){return false;}int[][] dp=new int[nums.length][sum/2];for(int i=0;i<nums.length;i++){dp[i][0]=0;}for(int j=0;j<sum/2;j++){if(nums[0]<j){dp[0][j]=0;}else{dp[0][j]=nums[0];}}for(int i=1;i<nums.length;i++){for(int j=0;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]);}if(dp[i][j]==sum/2){return true;}else if(dp[i][j]>sum/2){continue;}}}return false;}
}

---

class Solution {public boolean canPartition(int[] nums) {Arrays.sort(nums);int sum=0;for(int i=0;i<nums.length;i++){sum+=nums[i];}if(sum%2!=0){return false;}int[] dp=new int[sum/2+1];for(int i=0;i<nums.length;i++){for(int j=sum/2;j>=nums[i];j--){dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);if(dp[j]==sum/2){return true;}}}return false; }
}