【动态规划】01背包问题：01背包，分割等和子集，目标和，最后一块石头的重量

文章目录1. 01背包DP 41题目描述解题思路方案一方案二代码实现2. 分割等和子集LC 416题目描述解题思路代码实现3. 目标和LC 494题目描述解题思路代码实现4. 最后一块石头的重量LC 1049题目描述解题思路代码实现01背包最典型的做题思路就是选或不选不需要考虑个数的问题1. 01背包DP 4101背包题目描述解题思路方案一状态表示dp[i][j]表示从前i个物品中选总体积不超过j所有选法的最大价值状态转移方程对于每一个物品都可以选或不选不选第i个物品dp[i][j] dp[i-1][j]选第i个物品当前物品的体积是v[i]也就是说选这个物品之前包中应该占用了j-v[i]的空间如果j-v[i]0说明可以选dp[i][j] w[i] dp[i-1][j-v[i]]二者取最大值dp[i][j] max(dp[i-1][j],dp[i-1][j-v[i]]w[i])初始化在dp表头多加一行多加一列方便i和j的编号一一映射方案二状态表示dp[i][j]表示从前i个物品中选总体积恰好为j所有选法的最大价值。如果不能找出恰好为j的方案就令dp[i][j] -1状态转移方程不选第i个物品当前一个选法存在也就是dp[i-1][j]-1才可以让dp[i][j] dp[i-1][j]选第i个物品如果j-v[i]0且dp[i-1][j-v[i]]0说明选这个物品之前体积为j-v[i]的选法存在dp[i][j] w[i] dp[i-1][j-v[i]]二者取最大值dp[i][j] max(dp[i-1][j],dp[i-1][j-v[i]]w[i])初始化在dp表头多加一行多加一列.j 0时表示t体积为0因此不选任何物品价值也都是0dp[i][0] 0;i 0,j0时不选择物品就不可能有体积因此当j0时dp[0][j] -1优化利用滚动数组做空间优化每次填表只需要用到第 i-1 行的数据因此可以用两个数组分别记录第i-1和第i行的数组就可以反复赋值一直到i n.进一步优化到用一个数组填完数据就可以更新每次用到的数据是dp[j]和dp[j-v[i]]由于dp[j-v[i]]在dp[j]之前此时这两个都是上一行的数据所以要从右往左填表代码实现importjava.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();intVin.nextInt();int[]vnewint[n1];int[]wnewint[n1];for(inti1;in;i){v[i]in.nextInt();w[i]in.nextInt();}int[][]dpnewint[n1][V1];//方案一for(inti1;in;i){for(intj1;jV;j){dp[i][j]dp[i-1][j];if(j-v[i]0)dp[i][j]Math.max(dp[i-1][j],w[i]dp[i-1][j-v[i]]);}}System.out.println(dp[n][V]);//方案二for(intj1;jV;j)dp[0][j]-1;for(inti1;in;i){for(intj1;jV;j){dp[i][j]dp[i-1][j];if(j-v[i]0dp[i-1][j-v[i]]0)dp[i][j]Math.max(dp[i-1][j],w[i]dp[i-1][j-v[i]]);}}if(dp[n][V]0)System.out.println(dp[n][V]);elseSystem.out.println(0);}}优化只需要在原来的代码基础上修改j遍历顺序从大到小删除dp表的横坐标即可importjava.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();intVin.nextInt();int[]vnewint[n1];int[]wnewint[n1];for(inti1;in;i){v[i]in.nextInt();w[i]in.nextInt();}int[]dpnewint[V1];//方案一for(inti1;in;i){for(intjV;j0;j--){if(j-v[i]0)dp[j]Math.max(dp[j],w[i]dp[j-v[i]]);elsebreak;}}System.out.println(dp[V]);//方案二for(intj1;jV;j)dp[j]-1;for(inti1;in;i){for(intjV;j0;j--){if(j-v[i]0dp[j-v[i]]0)dp[j]Math.max(dp[j],w[i]dp[j-v[i]]);}}if(dp[V]0)System.out.println(dp[V]);elseSystem.out.println(0);}}2. 分割等和子集LC 416分割等和子集题目描述解题思路把问题转换成在数组中选择一部分数使他们的和是sum/2状态表示dp[i][j]表示从前i个数中选所有选法中能否凑成j这个数状态转移方程不选i元素dp[i][j] dp[i-1][j];选i元素找到j-nums[i]即可dp[i][j] dp[i][j-nums[i]]上面两种方式取和dp[i][j] dp[i-1][j] || dp[i][j-nums[i]]初始化在dp表头多加一行多加一列j 0时表示总和为0也就是每个数都不选因此dp[i]][0]都是truei 0j0表示不选任何数凑成j不存在。因此j0时dp[0][j] false代码实现publicbooleancanPartition(int[]nums){intnnums.length;intsum0;for(inta:nums)suma;intmsum/2;if(sum%2!0)returnfalse;boolean[][]dpnewboolean[n1][m1];for(inti0;in;i)dp[i][0]true;for(inti1;in;i){for(intj1;jm;j){dp[i][j]dp[i-1][j];if(j-nums[i-1]0)dp[i][j]dp[i][j]||dp[i-1][j-nums[i-1]];}}returndp[n][m];}空间优化classSolution{publicbooleancanPartition(int[]nums){intnnums.length;intsum0;for(inta:nums)suma;intmsum/2;if(sum%2!0)returnfalse;boolean[]dpnewboolean[m1];dp[0]true;for(inti1;in;i){for(intjm;j0;j--){if(j-nums[i-1]0)dp[j]dp[j]||dp[j-nums[i-1]];}}returndp[m];}}3. 目标和LC 494目标和题目描述解题思路在数组中选出一部分数假设总和为a填另一部分总和为b填-那么a-btargeta b sum可以通过二元一次方程算出来a (targetsum)/2. 通过背包问题找到令a (targetsum)/2的选法就使最终答案状态表示dp[i][j] 表示从前i个元素中选总和恰好为j有多少种选法状态转移方程不选idp[i][j] dp[i-1][j]选ij-nums[i]dp[i][j] dp[i-1][j-nums[i]]上面两种选法的总和是dp[i][j]的值初始化dp表多加一行多加一列dp[0][0]表示不选任何数总和为0成立有一种选法。dp[0][0] 1i 0时dp[0][j]表示不选任何数凑成j不存在选法所以都为0省略初始化j 0时dp[i][0]表示从前i个数中选择一部份数总和为j而j可能为0不能统一初始化j 0时除非nums[i]0其他情况不会越界访问nums[i]0时访问的就是dp[i-1][0]也不会造成越界访问因此这里不能初始化而是放在后续的填表中解决。代码实现publicintfindTargetSumWays(int[]nums,inttarget){intnnums.length;intsum0;for(inta:nums)suma;intm(sumtarget)/2;if(m0||(sumtarget)%2!0)return0;int[][]dpnewint[n1][m1];dp[0][0]1;for(inti1;in;i){for(intj0;jm;j){dp[i][j]dp[i-1][j];if(jnums[i-1])dp[i][j]dp[i-1][j-nums[i-1]];}}returndp[n][m];}优化publicintfindTargetSumWays(int[]nums,inttarget){intnnums.length;intsum0;for(inta:nums)suma;intm(sumtarget)/2;if(m0||(sumtarget)%2!0)return0;int[]dpnewint[m1];dp[0]1;for(inti1;in;i){for(intjm;jnums[i-1];j--){dp[j]dp[j-nums[i-1]];}}returndp[m];}4. 最后一块石头的重量LC 1049最后一块石头的重量题目描述解题思路先把数字换成字母可以很容易发现这题和上一题的添加符号类似选出一部分数假设总和为a,填另一部分假设总和为b填-使得最终的差值尽量小。差值最小的情况就是a与b最接近的时候如果ab则没有石头剩下返回0。因此这个题可以转换成选出一部分数使得和尽可能接近sum/2。nums[i]既是价值也是体积背包容量相当于sum/2状态表示dp[i][j] 表示在前i个数中选择总体积不超过j的最大价值状态转移方程不选i元素dp[i][j] dp[i-1][j]选i元素j nums[i]dp[i][j] dp[i-1][j-nums[i]]以上两种情况取最大值代码实现classSolution{publicintlastStoneWeightII(int[]stones){intnstones.length;intsum0;for(inta:stones)suma;intmsum/2;int[][]dpnewint[n1][m1];for(inti1;in;i){for(intj1;jm;j){dp[i][j]dp[i-1][j];if(jstones[i-1])dp[i][j]Math.max(dp[i][j],dp[i-1][j-stones[i-1]]stones[i-1]);}}intadp[n][m];intbsum-dp[n][m];returnMath.abs(a-b);}}优化publicintlastStoneWeightII(int[]stones){intnstones.length;intsum0;for(inta:stones)suma;intmsum/2;int[]dpnewint[m1];for(inti1;in;i){for(intjm;jstones[i-1];j--){dp[j]Math.max(dp[j],dp[j-stones[i-1]]stones[i-1]);}}intadp[m];intbsum-dp[m];returnMath.abs(a-b);}