网站空间不续费,泰兴中信建设有限责任公司,wordpress中文博客,财经那个网站做的好前言
zaccheo打卡代码随想录第35天 由于这段时间工作太忙了#xff08;加上我的懒病犯了#xff09;导致迟打卡了好几天555555.。。。
今天的主要是动态规划中的背包问题#xff0c;这个真的是蛮难理解的#xff0c;我把我自己强行按在椅子上半个小时一点一点的看卡哥文章…前言
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 sum0;for(int i0;inums.length;i){sumnums[i];}if(sum%2!0){return false;}int[][] dpnew int[nums.length][sum/2];for(int i0;inums.length;i){dp[i][0]0;}for(int j0;jsum/2;j){if(nums[0]j){dp[0][j]0;}else{dp[0][j]nums[0];}}for(int i1;inums.length;i){for(int j0;jsum/2;j){if(jnums[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 sum0;for(int i0;inums.length;i){sumnums[i];}if(sum%2!0){return false;}int[] dpnew int[sum/21];for(int i0;inums.length;i){for(int jsum/2;jnums[i];j--){dp[j]Math.max(dp[j],dp[j-nums[i]]nums[i]);if(dp[j]sum/2){return true;}}}return false; }
}
