2023年8月1日发(作者：)

01背包问题分⽀之背包刚好装满时获取最⼤价值的物品01背包问题：指在背包装载重量有限的情况下，挑选不同重量物品。物品⾝具两种属性，⼀个是本⾝价值，⼀个是本⾝重量。⽽01背包指挑选重量相加后⼩于等于背包承重，且价值最⼤的东西总和。⽽今天做leetcode的每⽇⼀题刚好做到01背包相关解法的题⽬：常规做法是暴⼒破解，我本⾝的想法也类似，通过回溯法完成了，但是花费的时间和空间⼤⼩⽐较⼤（如图下）故想去进⾏优化，仔细琢磨题意想到：把数组分成两个⼦集，⼀个作为正数累加起来做正⼦集A，⼀个作为负数累加起来做负⼦集B，⽽按题意A-B=target，然后左右添加上整个数组nums累加和sum（即A+B），得A-B+sum=target+sum;化简可得2A=target+sum。可以得出结论：我们的⽬标是在数组中找出⼀个⾮连续⼦集相加后乘以2等于⽬标+数组本⾝的累加和。转化为背包问题就是，对数组内每个数字进⾏挑选（选，不选），最终相加结果刚好等于我们的⽬标target因为在该题上，数字本⾝即是价值也是重量，故对于当前nums[i]值有多少种⽅案到达数值j，即可以通过上层的dp[i-1][j]，即之前的⽅案累加和，以及上层j-nums[i]位置的⽅法累加和获得（但该⽅法的前提是j必须⼤于nums[j]）,故dp[i][j]⽅案就是两者累加起来（i为数组nums的下标，j为当前的target值）⽽状态转移⽅程为：dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j]class Solution { public int findTargetSumWays(int[] nums, int target) { //正⼦集-负⼦集=⽬标->左右加⼀个正⼦集和负⼦集即全集->2*正⼦集=⽬标+全集 int sum=0; for(int a:nums) sum+=a; if((sum+target)%2==1||target>sum) return 0; int len=; target=(sum+target)/2; int [][]dp=new int[len+1][target+1]; //01背包 dp[0][0]=1; for(int i=1;i=nums[i-1]) dp[i][j]+=dp[i-1][j-nums[i-1]]; } } return dp[len][target]; }}代码如上，结果如下，很明显⽤了动态规划速度快乐很多很多，但是空间上浪费了很多，但换个⽅程式应该是可以降为⼀维数组从⽽降低空间复杂度，⽐如i的第0⾏纯属浪费掉。该题重点在于，每⼀列，即对于背包当前的承重量，数组是延续之前的⽅案⽽不是归0,。⽽对于背包刚好装满，状态转移⽅程基本避不开**dp[i][j]+=dp[i-1][j-nums[i-1]];**这条核⼼⽅程。

2023年8月1日发(作者：)

01背包问题分⽀之背包刚好装满时获取最⼤价值的物品01背包问题：指在背包装载重量有限的情况下，挑选不同重量物品。物品⾝具两种属性，⼀个是本⾝价值，⼀个是本⾝重量。⽽01背包指挑选重量相加后⼩于等于背包承重，且价值最⼤的东西总和。⽽今天做leetcode的每⽇⼀题刚好做到01背包相关解法的题⽬：常规做法是暴⼒破解，我本⾝的想法也类似，通过回溯法完成了，但是花费的时间和空间⼤⼩⽐较⼤（如图下）故想去进⾏优化，仔细琢磨题意想到：把数组分成两个⼦集，⼀个作为正数累加起来做正⼦集A，⼀个作为负数累加起来做负⼦集B，⽽按题意A-B=target，然后左右添加上整个数组nums累加和sum（即A+B），得A-B+sum=target+sum;化简可得2A=target+sum。可以得出结论：我们的⽬标是在数组中找出⼀个⾮连续⼦集相加后乘以2等于⽬标+数组本⾝的累加和。转化为背包问题就是，对数组内每个数字进⾏挑选（选，不选），最终相加结果刚好等于我们的⽬标target因为在该题上，数字本⾝即是价值也是重量，故对于当前nums[i]值有多少种⽅案到达数值j，即可以通过上层的dp[i-1][j]，即之前的⽅案累加和，以及上层j-nums[i]位置的⽅法累加和获得（但该⽅法的前提是j必须⼤于nums[j]）,故dp[i][j]⽅案就是两者累加起来（i为数组nums的下标，j为当前的target值）⽽状态转移⽅程为：dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j]class Solution { public int findTargetSumWays(int[] nums, int target) { //正⼦集-负⼦集=⽬标->左右加⼀个正⼦集和负⼦集即全集->2*正⼦集=⽬标+全集 int sum=0; for(int a:nums) sum+=a; if((sum+target)%2==1||target>sum) return 0; int len=; target=(sum+target)/2; int [][]dp=new int[len+1][target+1]; //01背包 dp[0][0]=1; for(int i=1;i=nums[i-1]) dp[i][j]+=dp[i-1][j-nums[i-1]]; } } return dp[len][target]; }}代码如上，结果如下，很明显⽤了动态规划速度快乐很多很多，但是空间上浪费了很多，但换个⽅程式应该是可以降为⼀维数组从⽽降低空间复杂度，⽐如i的第0⾏纯属浪费掉。该题重点在于，每⼀列，即对于背包当前的承重量，数组是延续之前的⽅案⽽不是归0,。⽽对于背包刚好装满，状态转移⽅程基本避不开**dp[i][j]+=dp[i-1][j-nums[i-1]];**这条核⼼⽅程。