网站建设需求精确表,优秀网站欣赏,wordpress 首页变量,金山办公给我发验证码一、1049. 最后一块石头的重量 II
1.思路#xff1a;01背包问题#xff0c;其中dp[j]表示容量为j的背包#xff0c;最多可以背最大重量为dp[j]。
2.注意#xff1a;递推公式dp[j] max(dp[j], dp[j - stones[i]] stones[i]);本题中的重量就是价值#xff0c;所以第二个…一、1049. 最后一块石头的重量 II
1.思路01背包问题其中dp[j]表示容量为j的背包最多可以背最大重量为dp[j]。
2.注意递推公式dp[j] max(dp[j], dp[j - stones[i]] stones[i]);本题中的重量就是价值所以第二个stone[i]表示价值的意思 遍历顺序上仍然是先物品后背包
3.本题与分割等和子集类似不同就在于最后return时本题得到的target sum / 2 因为是向下取整所以sum - dp[target] 一定是大于等于dp[target]。
所以相撞也就是将target与sum - dp[target]作差即可。
class Solution {public int lastStoneWeightII(int[] stones) {if (stones.length 0 || stones null)return 0;int sum 0;// 先求出这堆石头的和以便得到背包能背的最大重量for (int stone : stones) {sum stone;}int target sum 1;int[] dp new int[target 1];// for循环 先物品再背包for (int i 0; i stones.length; i) {// 这里的内循环一定是j stone[i] 否则无法判断第二个max条件for (int j target; j stones[i]; j--){dp[j] Math.max(dp[j], dp[j - stones[i]] stones[i]);}}return sum - 2 * dp[target];}
}
二、完全背包
1.有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品都有无限个也就是可以放入背包多次求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是每种物品有无限件。
2.核心代码区别于01背包的一维滚动数组差别就是内循环
for(int i 0; i weight.size(); i) { // 遍历物品for(int j bagWeight; j weight[i]; j--) { // 遍历背包容量dp[j] max(dp[j], dp[j - weight[i]] value[i]);}
}
3.计算过程 3.518. 零钱兑换 II
1.思路完全背包。
2.递推公式dp[j] dp[j - nums[i]]表示填满j包括j这么大容积的包有dp[j]种方法。
例如dp[j]j 为5
已经有一个1nums[i] 的话有 dp[4]种方法 凑成 容量为5的背包。已经有一个2nums[i] 的话有 dp[3]种方法 凑成 容量为5的背包。已经有一个3nums[i] 的话有 dp[2]中方法 凑成 容量为5的背包已经有一个4nums[i] 的话有 dp[1]中方法 凑成 容量为5的背包已经有一个5 nums[i]的话有 dp[0]中方法 凑成 容量为5的背包
那么凑整dp[5]有多少方法呢也就是把 所有的 dp[j - nums[i]] 累加起来。
3.注意该题纯完全背包是能凑成总和就行不用管怎么凑的不需要管顺序。
4.代码
class Solution {public int change(int amount, int[] coins) {// dp[j] 表示填满j包括j这么大容积的包有dp[j]种方法int[] dp new int[amount1];//初始化dp数组表示金额为0时只有一种情况也就是什么都不装dp[0] 1;for (int i 0; i coins.length; i) { // 零钱的种类数for (int j coins[i]; j amount; j){ // 组合方法dp[j] dp[j - coins[i]];}}return dp[amount];}
}
