【随想录】Day44—第九章 动态规划part06

本文主要是介绍【随想录】Day44—第九章 动态规划part06，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

题目1: 完全背包

• 题目链接：52. 携带研究材料

---

1- 什么是完全背包问题？

• 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]);}
}

• 在完全背包中如果希望物品使用无限次，此时需要修改遍历的顺序，正序遍历即可实现每个物品使用无限次。
• 我们知道 01背包 内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
• 而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

• dp状态图如下：

相信很多同学看网上的文章，关于完全背包介绍基本就到为止了。
其实还有一个很重要的问题，为什么遍历物品在外层循环，遍历背包容量在内层循环？
这个问题很多题解关于这里都是轻描淡写就略过了，大家都默认 遍历物品在外层，遍历背包容量在内层，好像本应该如此一样，那么为什么呢？
难道就不能遍历背包容量在外层，遍历物品在内层？

---

先遍历物品 和 先遍历背包的区别

• 1. 先遍历物品 再 遍历背包
• 对于 coins = {1,2,5} 此时最后的结果只能出现 {1,2} 不会出现 {2,1} 的情况
• 2. 先遍历背包 再 遍历物品
• 最终得到的是排列数

---

动规五部曲

• 1. 定义 dp 数组以及其含义
  • dp[i] 代表，容量为 i 的背包的最大效益
• 2. 递推公式
  • dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
• 3. dp 数组初始化
  • dp[0] = 0
• 4.确定遍历顺序
  • ① 先遍历物品：i 从 0 遍历到 物品的个数 n
  • ② 后遍历背包：j 从背包重量 weight[i] 遍历到 v

---

2- 题解

⭐ 完全背包——题解思路

import java.util.Scanner;
public class Main {public static void main(String[] args) {int n = 0;int v = 0;Scanner sc = new Scanner(System.in);n = sc.nextInt();  // 物品v = sc.nextInt();  // 背包重量// 初始化 weight 数组 和 value 数组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();}// 1. 定义 dp 数组int[] dp = new int[v+1];// 2. 确定递推公式// dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);// 3. 初始化dp[0] = 0;for(int i = 0 ; i < n;i++){ // 遍历物品for(int j = weight[i]; j <= v ;j++){dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);}}System.out.println(dp[v]);}
}

---

题目2: 518. 零钱兑换 II

• 题目链接：518. 零钱兑换 II

---

1- 思路

动规五部曲

• 1. 确定 dp 数组含义
  • dp[j]：凑成总金额j的货币组合数为dp[j]
• 2. 确定递推公式
  • dp[j] += dp[j-coins[i]]
• 3. dp 数组初始化
  • dp[0] = 1
• 4. 遍历顺序
  • ① 先遍历物品：i 从 0 遍历到 物品的个数 coins.length
  • ② 后遍历背包：j 从背包重量 coins[i] 遍历到 amount

---

---

2- 题解

⭐零钱兑换 II ——题解思路

class Solution {public int change(int amount, int[] coins) {// 维度 1 target = amount// 维度 2 面额 = coins// 目的：根据面额凑出 target // 1. 定义 dp 数组 //  达到 target 需要的组合种类数 int[] dp = new int[amount+1];// 2. 确定递推公式// 3. 初始化dp[0] = 1;// 4. 遍历顺序// 先物品后背包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];}
}

---

题目3: 377. 组合总和 Ⅳ

• 题目链接：377. 组合总和 Ⅳ

---

本题目和零钱兑换 II 的区别：

• 零钱兑换不强调元素的顺序，即 1,1,2 和 1,2,1 实际上是按照一种情况来算
• 但在本题目中， 1,1,2 和 1,2,1 需要进行分别计算

注意：

• ① 先遍历物品再遍历背包： 得到的是组合数
• ② 先遍历背包再遍历物品：得到的是排列数

1- 思路

动规五部曲

• 1. 确定 dp 数组含义
  • dp[j]：凑成总金额j的货币组合数为dp[j]
• 2. 确定递推公式
  • dp[j] += dp[j-coins[i]]
• 3. dp 数组初始化
  • dp[0] = 1
• 4. 遍历顺序（所求为组合，因此需要先遍历背包再遍历物品）
  • 背包：i 从 0 遍历到 target ，即for(int i = 0 ; i <=target ; i++)
  • 物品：j 从 0 遍历到 nums.length ，即 for(int j = 0 ; j <= nums.length; j++)

---

2- 题解

⭐组合总和 Ⅳ——题解思路

class Solution {public int combinationSum4(int[] nums, int target) {// 物品： nums.length// 背包： targetint n = nums.length;// 1. 定义 dp 数组int[] dp = new int[target+1];// 2. 递推公式// dp[j] += dp[j-weight[i]]// 3. 初始化dp[0] = 1;// 4.遍历顺序// 遍历 物品// 遍历 背包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];}
}

---

这篇关于【随想录】Day44—第九章 动态规划part06的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---