代码随想录 刷题记录-19 动态规划（3）完全背包理论、习题

本文主要是介绍代码随想录 刷题记录-19 动态规划（3）完全背包理论、习题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、完全背包理论

52. 携带研究材料

有N种物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

首先从二维dp上来讲：

1.dp数组及下标含义：

        dp[i][j] : 考虑前 i种物品，背包容量为j时所能装入的最大价值

2.递推公式

        dp[i][j] = Math.max( dp[i-1][j] , dp[i][j-weight[i]] + value[i] )

注意这里与01背包不同的是，每种物品可以取无限多次，公式右边的第一项代表不考虑物品i的情况，公式右边第二项代表考虑物品i 1个或多个的情况，由于是依赖于本行的值，当第一次进入时如果选择右边就是拿了1个，第二次在j增加后还选择右边，依赖的左边的本行值已经更新过了，所以再次选择右边就包括了多个的情况，即右边这一项是物品无限件的体现，它的核心在于使用本行的值而不是上一行的值进行更新。

3.初始化

        根据递推公式，计算时依赖于上一行和本行左边，对物品为0的第一行进行初始化，当 j >= weight[0] 时， dp[0][j] = dp[0][j-weight[0]] +value[0]

4.遍历顺序

        先物品后容量 或者 先容量或物品都可以，这里先物品后容量

        正序遍历，因为需要用到本行左边已经计算的值。

5.dp模拟

代码如下：

import java.util.Scanner;public class Main{public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int capacity = scanner.nextInt();int[] weight = new int[n];int[] value = new int[n];for(int i = 0; i < n ; i++){weight[i] = scanner.nextInt();value[i] = scanner.nextInt();}int[][] dp = new int[n][capacity+1];for(int j = weight[0]; j <= capacity ; j++){dp[0][j] = dp[0][j-weight[0]] + value[0];}for(int i = 1 ; i < n ; i++){for(int j = 0; j <= capacity ; j++){if(j < weight[i]) dp[i][j] = dp[i-1][j];else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);}}System.out.println(dp[n-1][capacity]);}
}

接下来考虑使用滚动数组的情况：

01背包和完全背包唯一不同就是体现在遍历顺序上，这里直接针对遍历顺序进行分析。

首先再回顾一下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]);}
}

即完全背包恰好利用了01背包如果正序遍历则会覆盖的特点，因为完全背包需要的数据是本行的左边，这要求左边必须计算过，所以要中序遍历。

也是因为完全背包对背包容量是正序遍历的，这也就导致了他的物品循环和背包容量循环的嵌套顺序是可以互换的（在二维里相当于从左到右一列一列的，所需要的数据在本行左边和上边，已经计算过了）

代码如下：

import java.util.Scanner;public class Main{public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int capacity = scanner.nextInt();int[] weight = new int[n];int[] value = new int[n];for(int i = 0; i < n ; i++){weight[i] = scanner.nextInt();value[i] = scanner.nextInt();}int[] dp = new int[capacity+1];for(int i = 0 ; i < n ; i++){for(int j = weight[i]; j <= capacity ; j++){dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);}}System.out.println(dp[capacity]);}
}

二、习题

1.518.零钱兑换II

回溯法，但是会超时：

class Solution {int[] coins;int sum = 0;int amount;int result = 0;public int change(int amount, int[] coins) {this.coins = coins;this.amount = amount;dfs(0);return result;}public void dfs(int startIndex){if(sum == amount){result++;return;}if(sum > amount){return ;}for(int i = startIndex ; i < coins.length ; i++){sum += coins[i];dfs(i);sum -= coins[i];}}
}

考虑动态规划：

每个钱币能选择的数量不限，属于完全背包问题。

本题和纯完全背包不一样，纯完全背包是凑成背包最大价值是多少，而本题是要求凑成总金额的物品组合个数。

注意这里属于组合数，而不是排列数。

动规五步曲:

1.dp数组及下标含义

dp[j] : 当前遍历的前i种钱币中，容量为j下有 dp[j] 种方案凑满。

2.递推公式

dp[j]  += dp[j - coins[i]]

这个递推公式大家应该不陌生了，我在讲解01背包题目的时候在这篇494. 目标和 中就讲解了，求装满背包有几种方法，公式都是：dp[j] += dp[j - nums[i]];

3.初始化

dp[0] = 1;

首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话，后面所有推导出来的值都是0了。

那么 dp[0] = 1 有没有含义，其实既可以说 凑成总金额0的货币组合数为1，也可以说 凑成总金额0的货币组合数为0，好像都没有毛病。

但题目描述中，也没明确说 amount = 0 的情况，结果应该是多少。

这里我认为题目描述还是要说明一下，因为后台测试数据是默认，amount = 0 的情况，组合数为1的。

下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]

dp[0]=1还说明了一种情况：如果正好选了coins[i]后，也就是j-coins[i] == 0的情况表示这个硬币刚好能选，此时dp[0]为1表示只选coins[i]存在这样的一种选法。

4.遍历顺序

外层是钱币种类。

内层是容量。

因为可选是无限次，所以正序。

在滚动数组下，必须外层是钱币种类，内层是容量，这样求出来的是组合数，反之求出的是排列数：

or

or

在二维dp数组下，遍历的内外层顺序可以交换。

5.dp模拟

代码如下：

public int change(int amount, int[] coins) {int[] dp = new int[amount+1];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];}

2.377. 组合总和 Ⅳ

本题是完全背包+排列数量和 问题，本题题目要求组合数，但是指出顺序不同的是不同组合，其实就是求排列数。

在学习回溯算法专题的时候，一定做过这两道题目回溯算法：39.组合总和 和回溯算法：40.组合总和II会感觉这两题和本题很像。

但其本质是本题求的是排列总和，而且仅仅是求排列总和的个数，并不是把所有的排列都列出来。

如果本题要把排列都列出来的话，只能使用回溯算法爆搜。

动规五部曲分析如下：

1.dp数组及下标含义：

dp[j] : 凑成正整数为j的排列个数 为 dp[j]

2.确定递推公式

dp[j] += dp[j - nums[i]]

3.初始化

dp[0] = 1

4.遍历顺序

因为是求排列数，所以先遍历容量，再遍历物品，这样排列不同的算作不同。

由于每个物品可以用无限次，对容量正序遍历。

5.dp模拟

3.57. 爬楼梯

这其实是一个完全背包问题。

1阶，2阶，.... m阶就是物品，楼顶就是背包。

每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。

问跳到楼顶有几种方法其实就是问装满背包有几种方法。

动规五部曲：

1.dp数组及下标含义

dp[j] : 到第j层有 dp[j] 种方法

2.递推公式

dp[j] += dp[j-i]   i从1到m进行遍历

3.初始化

dp[0] = 1;

4.遍历顺序

先跨1层后跨2层 与 先跨2层后跨1层 是不一样的方案，所以求的是排列数，外层容量，内层物品。

完全背包，正序遍历。

5.dp模拟

3.322. 零钱兑换

完全背包问题

动规五部曲：

1.dp数组及下标含义:

dp[j] ：凑足金额j所需要的最少的硬币个数为 dp[j] 个

2.递推公式

dp[j] = Math.min(dp[j] , dp[j-i] +1)

3.初始化

凑足金额0所需要的硬币个数为0，所以dp[0] = 0。

考虑到递推公式取最小值，初始化的值必须不影响取最小的操作，所以除了dp[0]以外初始化成Interger.MAX_VALUE，否则就有可能在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。

4.遍历顺序

本题并不强调集合是组合还是排列。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

在动态规划专题我们讲过了求组合数是动态规划：518.零钱兑换II (opens new window)，求排列数是动态规划：377. 组合总和 Ⅳ (opens new window)。

所以本题的两个for循环的关系是：外层for循环遍历物品，内层for遍历背包或者外层for遍历背包，内层for循环遍历物品都是可以的！

本题是背包问题，背包容量遍历是正序。

5.dp模拟

以输入：coins = [1, 2, 5], amount = 5为例

dp[amount]为最终结果。

代码如下：

（注意在递推时要排除初始值的影响）

dp[j] = Math.mim(dp[j], dp[j-coins[i] +1 ) ,如果不判断是否是Integer.MAX_VALUE的话，dp[j-coins[i]] +1可能移除，为负值，影响递推结果。

for(int i = 0 ; i < coins.length ; i++){for(int j = coins[i] ; j <= amount ; j++){if(dp[j - coins[i]]!=Integer.MAX_VALUE)dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);}}

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];dp[0] = 0;for(int i = 1 ; i < dp.length ; i++){dp[i] = Integer.MAX_VALUE;}for(int i = 0 ; i < coins.length ; i++){for(int j = coins[i] ; j <= amount ; j++){if(dp[j - coins[i]]!=Integer.MAX_VALUE)dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);}}return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount] ;}
}

4.279.完全平方数

完全背包问题

1.dp数组及下标含义

dp[j]：组成数j最少需要 dp[j]个完全平方数

2.递推公式

dp[j] = Math.min(dp[j] , dp[j - nums[i]] + 1)

3.初始化

dp[0] = 0;

dp的其他元素初始化成Integer.MAX_VALUE

4.遍历顺序

外层物品，内层背包容量，可以交换。

完全背包，容量正序遍历。

5.dp模拟

已输入n为5例，dp状态图如下：

代码如下：

class Solution {public int numSquares(int n) {int[] dp = new int[n+1];dp[0] = 0;for(int i = 1 ; i <=n  ; i++){dp[i] = Integer.MAX_VALUE;}for(int i = 0; i*i <= n ; i++){for(int j = i*i ; j <= n ; j++){if(dp[j - i*i] != Integer.MAX_VALUE) dp[j] = Math.min(dp[j], dp[j-i*i]+1);}}return dp[n];}
}

总结

本周的主题其实就是背包问题中的遍历顺序！

我这里做一下总结：

求组合数：动态规划：518.零钱兑换II (opens new window)求排列数：动态规划：377. 组合总和 Ⅳ (opens new window)、动态规划：70. 爬楼梯进阶版（完全背包） (opens new window)求最小数：动态规划：322. 零钱兑换 (opens new window)、动态规划：279.完全平方数(opens new window)

此时我们就已经把完全背包的遍历顺序研究的透透的了！

5.139.单词拆分

可以使用回溯法，会时间超限

考虑动态规划

1.dp数组及下标含义：

dp[i] : dp[i] 为true 表示前i个字符组成的字符串可以分割成字典中字符串。

2.递推公式

如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。

所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

for(int j = 0; j < i ; j++){if(dp[j] && check(j,i)) dp[i] = true;
}

3.初始化

从递推公式看出，dp[i] 依赖于 在dp数组中其前面的元素。

故dp[0] 必须为 true

dp[0] = true;

dp[0]有没有意义呢？

dp[0]表示如果字符串为空的话，说明出现在字典里。

但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况，那么dp[0]初始为true完全就是为了推导公式。

下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

4.遍历顺序

字典中的字符串可以使用多次，属于完全背包，正序遍历。

本题对顺序有要求，属于排列，需要外层遍历物品，内层遍历背包。

5.dp模拟

class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> set = new HashSet<>(wordDict);boolean[] dp = new boolean[s.length()+1];dp[0] = true;for(int i = 1; i <= s.length() ; i++){for(int j = 0;  j < i ; j++){if(dp[j] && set.contains(s.substring(j,i))) dp[i] = true;}}return dp[s.length()];}
}

这篇关于代码随想录 刷题记录-19 动态规划（3）完全背包理论、习题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---