北京网站开发哪家公司好,连云港做电商网站的公司,上海优秀网站建设公司,wordpress 会员登录可见参考资料#xff1a;代码随想录
题目链接#xff1a;. - 力扣#xff08;LeetCode#xff09;
这道题是01背包问题的抽象#xff0c;这道题的难点在于怎么绕明白遍历顺序是从后往前。
题目中给的nums数组#xff0c;以nums[1,5,11,5]为例#xff0c;可以分析为有4个物…参考资料代码随想录
题目链接. - 力扣LeetCode
这道题是01背包问题的抽象这道题的难点在于怎么绕明白遍历顺序是从后往前。
题目中给的nums数组以nums[1,5,11,5]为例可以分析为有4个物品每个物品的重量为weight[1,5,11,5],每个物品的价值为value[1,5,11,5]
最大容量为15115/2
1.确定dp数组含义
重量从0到maxWeight分别能装的最大价值
2.初始化dp数组
全部初始化为0
3.确定遍历顺序
只能选取一次从后向前
4.确定递推公式
class Solution {public boolean canPartition(int[] nums) {//求最大重量int sum 0;for(int num:nums){sumnum;}if(sum%2 ! 0) return false;int maxWeight sum/2;//1.确定dp数组含义int[] dp new int[maxWeight1];//2.初始化dp数组//3.确定遍历顺序for(int i 0;i nums.length;i){for(int j maxWeight;j nums[i] ;j--){//4.确定递推公式if(j nums[i]){dp[j] Math.max(dp[j],dp[j-nums[i]]nums[i]);}}}return dp[maxWeight] maxWeight;}
}
