KamaCoder 52 携带研究材料
题目链接：52.携带研究材料
文档讲解：代码随想录
视频讲解：携带研究材料
思路与感想：这道题目是一道纯完全背包题，携带研究材料在之前纯01背包题目的时候已经做过了，区别就在于物品能不能重复选。首先对于二维DP数组写法，题意的改动造成了代码的两处修改。第一处就是在DP数组的第一行初始化上，由于物品可以重复选择了，所以不像之前01背包遇到能放物品0的容量就把dp值置为物品0的value就一劳永逸了，这里需要考量的是背包容量能放几个物品0就尽可能放。所以代码是dp[0][i] = dp[0][i - weight[0]] + value[0];这个代码是比较巧妙的，一开始看还怕如果物品0重量不是1而是2或者3，造成背包中不是连续装物品0会不会出错，但事实上这个代码考虑到了这一点，所以在举例子的时候也可以按照预想思路填充背包。第二处修改在于递推公式上，由于物品可以重复选择，所以求最大值时，在选择物品i的情况下，在为背包预留了物品i的空间后，仍然可以在0-i物品中选择，所以递推公式就是dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - weight[i]] + value[i])。区别就是选择物品i后，不是i-1了而依旧是i。那对于一维DP滚动数组写法呢，除了这两个区别外，还有一处区别是遍历背包的时候必须正序遍历了，因为物品可以重复选，value可以重复加，而不是之前只能选一次，而且正因为这个遍历顺序都为正序了，遍历物品和遍历背包的两层for循环也可以颠倒了。以上就是纯完全背包代码的修改，总体而言还是跟01背包非常相像的，有了01背包的基础理解起来还是很轻松的。
收获：1.理解纯完全背包的变化
// 二维DP数组 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 接收物品种类数量 int bagSpace = sc.nextInt(); // 接收背包最大容量 int[] weight = new int[n]; // 记录每个物品的重量 int[] value = new int[n]; // 记录每个物品的价值 for (int i = 0; i < n; i++) { // 接收物品的重量和价值数组 weight[i] = sc.nextInt(); value[i] = sc.nextInt(); } int[][] dp = new int[n][bagSpace + 1]; // 定义dp数组，dp[i][j]下标含义为从0-i物品中任选，可重复选择，背包容量j能装的最大价值。顺便初始化第一列都为因为背包容量0什么也装不了 for (int i = weight[0]; i < bagSpace + 1; i++) { // 初始化第一行，自能装物品0开始，只要背包容量有空余就装物品0 dp[0][i] = dp[0][i - weight[0]] + value[0]; } for (int i = 1; i < n; i++) { // 遍历物品和背包顺序都要正序，谁外谁内无所谓，物品0已经初始化，从物品1开始遍历 for (int j = 0; j < bagSpace + 1; j++) { // 遍历背包正序是保证每个物品可以重复选择 if (j >= weight[i]) { dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - weight[i]] + value[i]); // 可以选择。不放物品i就是从0-(i-1)物品中选，放物品i要事先预留背包容量-weight[i]，但依然是从0-i物品中选择，因为每个物品可以重复选，然后加上物品i的value } else { dp[i][j] = dp[i - 1][j]; // 背包容量放不了物品i，无法选择 } } } System.out.println(dp[n - 1][bagSpace]); sc.close(); } }// 一维DP滚动数组 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 接收物品种类数量 int bagSpace = sc.nextInt(); // 接收背包最大容量 int[] weight = new int[n]; // 记录每个物品的重量 int[] value = new int[n]; // 记录每个物品的价值 for (int i = 0; i < n; i++) { // 接收物品的重量和价值数组 weight[i] = sc.nextInt(); value[i] = sc.nextInt(); } int[] dp = new int[bagSpace + 1]; // 定义dp数组 for (int i = 0; i < n; i++) { // 遍历物品和背包顺序都要正序，谁外谁内无所谓 for (int j = weight[i]; j < bagSpace + 1; j++) { // 遍历背包正序是保证每个物品可以重复选择 dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i]); // 可以选择。不放物品i就是从0-(i-1)物品中选，放物品i要事先预留背包容量-weight[i]，但依然是从0-i物品中选择，因为每个物品可以重复选，然后加上物品i的value } } System.out.println(dp[bagSpace]); sc.close(); } }LeetCode 518 零钱兑换 Ⅱ
题目链接：518.零钱兑换 Ⅱ
文档讲解：代码随想录
视频讲解：零钱兑换 Ⅱ
思路与感想：一开始看到题目要求的东西：凑成总金额的方法数量，我一下子就想到昨天总结时的两道题目，一道是等和子集，这里面是看能不能装满背包，对应这里能不能凑满总金额。另一道是目标和，这里求的是装满这个容量left的背包有多少种方式，对应这里就是凑满总金额有多少种方式。根据题意我选择了用后者目标和的递推公式，然后由于硬币可以重复选所以用了完全背包的模板，再遍历背包的时候也正序遍历，不出意外题目就通过了。看卡哥视频讲解的时候才发现有一个细节我是没有注意到的，那就是遍历物品和背包两个for循环不能颠倒，因为题目求的是是零钱兑换的组合方式，所以一定要先遍历物品，这样在选择物品的时候方法情况里面只会出现12不会出现21，但是如果是先遍历背包再遍历物品，那每一个背包容量都会遍历一次12，那在方法情况中就可能出现21，那这样就会重复，相当于求的是排列情况了。所以这道题目一定要先遍历物品再遍历背包。
收获：1.完全背包应用；2.求组合与排列时完全背包的两层for循环内外有讲究
// 一维DP数组 class Solution { public int change(int amount, int[] coins) { int[] dp = new int[amount + 1]; // 定义DP数组，dp[j]含义为装满容量为j的背包一共有多少种方法 dp[0] = 1; // 初始化装满容量为j的背包有一种方法 for (int i = 0; i < coins.length; i++) { // 遍历物品 for (int j = coins[i]; j < amount + 1; j++) { // 遍历背包 dp[j] += dp[j - coins[i]]; // 递推累加。eg：遍历到coin = 1时，dp[4] = dp[5]；遍历到coin = 2时，dp[3] = dp[5]...围绕dp含义 } } return dp[amount]; } }LeetCode 377 组合总和 Ⅳ
题目链接：377.组合总和 Ⅳ
文档讲解：代码随想录
视频讲解：组合总和 Ⅳ
思路与感想：这道题目本质上还是求装满一个完全背包有多少种方法，与上一道题目的区别在于，上一题求的是组合，这一题看似题目求组合实则是求排列，那代码上的区别就确定了，那就是先遍历背包再遍历物品，都从0开始遍历，递推的时候加一个条件判断即可通过。
收获：1.装满一个背包有多少种方法的完全背包应用求排列
// 一维DP数组求排列 class Solution { public int combinationSum4(int[] nums, int target) { int[] dp = new int[target + 1]; // 定义dp数组，装满容量j的背包有多少种方法 dp[0] = 1; // 初始化 for (int j = 0; j < target + 1; j++) { // 求排列先遍历背包 for (int i = 0; i < nums.length; i++) { // 再遍历物品 if (j >= nums[i]) { // 容量大于i的占位空间才能加 dp[j] += dp[j - nums[i]]; // 递推累加 } } } return dp[target]; } }KamaCoder 57 爬楼梯
题目链接：57.爬楼梯
文档讲解：代码随想录
视频讲解：爬楼梯
思路与感想：这道题是之前爬楼梯的进阶版，从原来的只能爬1阶或2阶，到现在能够爬1-m阶，然后求爬到楼顶一共有多少种方式。题意是简单的，关键是要识别出进阶之后的爬楼梯实质上可以转换为完全背包，而且爬楼梯的不同方式实质上是求排列。总楼梯数可以看作完全背包容量，爬几阶可以看作物品，那就跟上一题一摸一样了。
收获：1.进阶爬楼梯转换为完全背包求排列
// 一维DP滚动数组求完全背包排序 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 接收楼梯总阶数 int m = sc.nextInt(); // 接收一次最多能爬多少阶 int[] dp = new int[n + 1]; // 定义dp数组，爬到第j阶一共有多少种方法 dp[0] = 1; // 初始化 for (int j = 0; j < n + 1; j++) { // 完全背包求排序先遍历背包 for (int i = 1; i < m + 1; i++) { // 再遍历物品，一次能爬的阶数 if (j >= i) { // 必须容量大于一次性能爬的阶数 dp[j] += dp[j - i]; // 递推累加 } } } System.out.println(dp[n]); sc.close(); } }今天的四道题目虽然是完全背包的开始，但是因为有了前面01背包的基础所以写的很快而且基本上靠自己就能全部AC掉。大概花了三个小时多一点。把昨天任务给补完了，今天还有一点完全背包的剩余以及了解一下多重背包，背包问题就算是收尾了，总体来讲还是01背包打基础的时候比较痛苦，过掉了之后难的就是背包的应用了，也就是如何把题意转换成背包场景，这是最难的，至于代码部分都是那么几套模板，对应不同递推公式。
