专业的建设企业网站公司,正规免费代理,深圳企业500强,怎么做论坛的网站代码随想录算法训练营第四十四天 | 完全背包 、零钱兑换 II 、组合总和 Ⅳ
完全背包
题目链接#xff1a;题目页面 (kamacoder.com)
解释一、01背包 一维 #xff1a;为什么要倒序遍历背包#xff1f;
首先要明白二维数组的递推过程#xff0c;然后才能看懂二维变一维的…代码随想录算法训练营第四十四天 | 完全背包 、零钱兑换 II 、组合总和 Ⅳ
完全背包
题目链接题目页面 (kamacoder.com)
解释一、01背包 一维 为什么要倒序遍历背包
首先要明白二维数组的递推过程然后才能看懂二维变一维的过程。
假设目前有背包容量为10可以装的最大价值 记为g(10)。
即将进来的物品重量为6。价值为9。 那么此时可以选择装该物品或者不装该物品。
如果不装该物品显然背包容量无变化这里对应二维数组其实就是取该格子上方的格子复制下来就是所说的滚动下来直接g【10】 g【10】这两个g【10】要搞清楚右边的g【10】是上一轮记录的也就是对应二维数组里上一层的值而左边是新的g【10】也就是对应二维数组里下一层的值。
如果装该物品则背包容量 g(10-6) g(4) 9 也就是 g(10) g(4) 6 ,这里的6显然就是新进来的物品的价值g(10)就是新记录的对应二维数组里下一层的值而这里的g(4)是对应二维数组里上一层的值通俗的来讲你要找到上一层也就是上一状态下 背包容量为4时的能装的最大价值用它来更新下一层的这一状态也就是加入了价值为9的物品的新状态。
这时候如果是正序遍历会怎么样 g(10) g(4) 6 这个式子里的g(4)就不再是上一层的了因为你是正序啊g(4) 比g(10)提前更新那么此时程序已经没法读取到上一层的g(4)了新更新的下一层的g(4)覆盖掉了这里也就是为啥有题解说一件物品被拿了两次的原因。
解释二、01背包到底先遍历物品还是先遍历背包呢
其实在二维的时候即使是先遍历背包重量再遍历物品重量你真的画图的时候会发现永远的数据来源依旧还是max(不放放 max(正上方的值左上角的值)。
那你在一维的时候如果先遍历背包容量的话:
如果你还是从左到右地遍历背包容量一样会造成重复添加
如果你从右到左地遍历背包容量相当于你的计算顺序是先竖着写完第四列再竖着写完第三列再竖着写完第二列。。。但你写第四列的时候第三列全部都是空的左边是没有数据的你永远只在累加正上方的数。而如果你是先遍历物品再遍历背包你的填空顺序是先写第一行从右往左写再写第二行的时候你的左边是有数字的。。。
那你可能想问我能不能做一个竖着的表格更新呢其实没有帮助的你只要先一股脑地竖着算你永远没法利用起左边格子的数字——无法利用之前格子的数那就不是动态规划了
解释三、为什么完全背包可以颠倒物品和背包的遍历顺序
请想像一下 01背包的二维dp数组图像 和 完全背包的二维dp数组图像
01背包 的二维数组dp[i] [j]只取决于其左上角的值所以 使用二维数组时可以从对物品和背包数组进行正序遍历且先物品还是先背包可以颠倒
01背包的一维数组dp[j] 因为
背包必须要倒序遍历参考上面解释一、01背包 一维 为什么要倒序遍历背包
↓
如果遍历背包容量放在上一层那么每个dp[j]就只会放入一个物品即背包里只放入了一个物品解释二
↓
所以要先物品后背包
完全背包其dp[j]完全取决于
// 先遍历物品再遍历背包
import java.util.*;public class Main {public static void main (String[] args) {Scanner sc new Scanner(System.in);int N sc.nextInt();int V sc.nextInt();int[] weights new int[N];int[] values new int[N];for(int i 0; i N; i) {weights[i] sc.nextInt();values[i] sc.nextInt();}int[] dp new int[V 1];for(int i 0; i N; i) {for(int j weights[i]; j V; j) {dp[j] Math.max(dp[j], dp[j - weights[i]] values[i]);}}System.out.println(dp[V]);}
}
// 先遍历背包再遍历物品
import java.util.*;public class Main {public static void main (String[] args) {Scanner sc new Scanner(System.in);int N sc.nextInt();int V sc.nextInt();int[] weights new int[N];int[] values new int[N];for(int i 0; i N; i) {weights[i] sc.nextInt();values[i] sc.nextInt();}int[] dp new int[V 1];for(int j 1; j V; j) {for(int i 0; i N; i) {if(j weights[i]) {dp[j] Math.max(dp[j], dp[j - weights[i]] values[i]);} }}System.out.println(dp[V]);}
}零钱兑换 II
题目链接518. 零钱兑换 II - 力扣LeetCode
这道题就是 494. 目标和 - 力扣LeetCode的完全背包版本
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
class Solution {public int change(int amount, int[] coins) {// 硬币数量不限 - 完全背包// dp[j] 表示填满j包括j这么大容积的包有dp[j]种方法int[] dp new int[amount 1];// dp[0] 1是 递归公式的基础。如果dp[0] 0 的话后面所有推导出来的值都是0了。dp[0] 1;// 因为纯完全背包求得装满背包的最大价值是多少和凑成总和的元素有没有顺序没关系即有顺序也行没有顺序也行// 而本题要求凑成总和的组合数元素之间明确要求没有顺序/**以coins[0] 1, coins[1] 5 amount 6为例先遍历物品就是先把1加入计算然后再把5加入计算 - 这样得到的是 组合先遍历背包背包容量的每一个值都是经过 1 和 5 的计算包含了{1, 5} 和 {5, 1}两种情况- 这样得到的是 排列 不理解的话可以打印dp数组来看看*/for(int i 0; i coins.length; i) {for(int j coins[i]; j amount; j) {dp[j] dp[j - coins[i]];}for(int ele : dp) {System.out.print(ele ,);}System.out.println( );}return dp[amount];}
} 组合总和 Ⅳ
题目链接377. 组合总和 Ⅳ - 力扣LeetCode
本题与动态规划518.零钱兑换II (opens new window)就是一个鲜明的对比一个是求排列一个是求组合遍历顺序完全不同
class Solution {public int combinationSum4(int[] nums, int target) {int[] dp new int[target 1];dp[0] 1;for (int i 0; i target; i) {for (int j 0; j nums.length; j) {if (i nums[j]) {dp[i] dp[i - nums[j]];}}}return dp[target];}
}
