医院网站建设宗旨,宁波seo费用,友情链接购买,推广模式有几种学习目标#xff1a; 学习动态规划 学习内容#xff1a;
01背包问题 学习时间#xff1a;
2025-06-17 周二晚上 学习产出#xff1a; 背包问题 01背包#xff1a;每件物品只能用一次#xff0c;对于每件物品#xff0c;即放或者不放。 完全背包#xff1a;物品可以一…学习目标 学习动态规划 学习内容
01背包问题 学习时间
2025-06-17 周二晚上 学习产出 背包问题 01背包每件物品只能用一次对于每件物品即放或者不放。 完全背包物品可以一直放。 01背包 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。 可以得到递推公式对于第i件物品对于重量为j的背包产生的最大价值为不放入该件物品时的最大价值dp[i-1][j]与放入该物品时的最大价值dp[i-1][j-weight[i]]values[i]的最大值即 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 如果我们把dp[i-1]的数据先copy到第i行那么得到递推公式 dp[i][j] max(dp[i][j], dp[i][j - weight[i]] value[i]); 那完全可以我们只维护一行数组每次遍历物品时用上一层的dp[j]来进行更新即可更新为一维数组递归公式为 dp[j] max(dp[j], dp[j - weight[i]] value[i]); 右边的dp[j]表示上一层即dp[i-1][j]得到的结果 注意如果用一维数组表示那么只能倒序才能保证每个物品只放入了一次具体可以自己推导。 416. 分割等和子集
解题思路 先求出目标和以及初始化dp[target]还是很直观。但是对于初次接触背包问题来讲在想dp[j]表示的涵义时没想明白。dp[j]应该表示为当背包最大容量为j时放入i和不放入i所能产生的最大价值是多少。如果最大容量为target且当前所能产生的最大价值为target时表示存在。转化为本题为加入在不超过当前最大和的情况下放入哪些元素能使的当前的目标和最大接近target class Solution { public boolean canPartition(int[] nums) { int sum 0;boolean result false;for(int i 0;inums.length;i) {sumnums[i];}if(sum % 2 ! 0) {return result;}int target sum / 2;int[] dp new int[target1];for(int i 0 ; i nums.length ; i) {for (int j target ; j nums[i] ; j--) {dp[j] Math.max(dp[j],dp[j-nums[i]]nums[i]);if(dp[j] target) {result true;}}}return result;
}}
