day46 完全背包理论基础 518. 零钱兑换 II 377. 组合总和 Ⅳ

完全背包理论基础

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

01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。

而完全背包的物品是可以添加多次的，所以要从小到大去遍历

动规五部曲

1.确定dp数组的定义

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2.一维dp数组的递推公式

dp[j]为 容量为j的背包所背的最大价值，那么如何推导dp[j]呢？

dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。

dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）

此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，

3.一维dp数组如何初始化

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

4.一维dp数组遍历顺序

因为物品有无限个所以内层循环可以正序遍历重复放入。

再来看看两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？

可以！

在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！因为两个for循环都是正序遍历，物品有无数个，先遍历物品与先遍历背包得到的结果是相同的，所以遍历顺序可以改变。因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。

// 先遍历物品，再遍历背包
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]);}
}

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

5.举例推导dp数组

52. 携带研究材料（典型完全背包问题）

在本题（现有代码基础上）中需要先遍历物品再遍历背包如果先遍历背包再遍历物品由于这个题目是在第一层循环内输入weight和value这样会导致多输入一组 数据（dp数组的长度为背包容量加1方便取到dp[w]，防止数组越界），解决：只有使用一次for循环（weight和value数组长度为n）来填充weight和value数组来存储数据再做操作即可(如下面第二段代码)。

代码

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

import java.util.*;
import java.lang.*;public class Main{public static void main (String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int w = in.nextInt();int[] dp = new int[w+1];int [] weight = new int [n];int [] value = new int [n];for (int i = 0; i < n; ++i) {int weights = in.nextInt();int values = in.nextInt();weight[i] = weights;value[i] = values;}// for(int num : weight){//     System.out.print(num+",");// }// System.out.println();// for(int nums : value){//     System.out.print(nums+",");// }for(int i = 0 ; i<= w ; i++){for(int j = 0; j < n; j++){if (i - weight[j] >= 0) dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);}}System.out.println(dp[w]);}
}

518. 零钱兑换 II  

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

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

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

组合不强调元素之间的顺序，排列强调元素之间的顺序。

动规五步曲

1.确定dp数组以及下标的含义

dp[j]：凑成总金额j的货币组合数为dp[j]

2.确定递推公式

dp[j] 就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加。

所以递推公式：dp[j] += dp[j - coins[i]];

只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。

例如：dp[j]，j 为5，

• 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
• 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
• 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
• 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
• 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包

那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。

3.dp数组如何初始化

首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话，后面所有推导出来的值都是0了。下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]。

4.确定遍历顺序

纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！

而本题要求凑成总和的组合数，元素之间明确要求没有顺序。

 外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况。（组合）

for (int i = 0; i < coins.size(); i++) { // 遍历物品for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量dp[j] += dp[j - coins[i]];}
}

假设：coins[0] = 1，coins[1] = 5。

那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

 外层for循环遍历背包（金钱总额），内层for遍历物品（钱币）的情况。（排列）

for (int j = 0; j <= amount; j++) { // 遍历背包容量for (int i = 0; i < coins.size(); i++) { // 遍历物品if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];}
}

背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。

5.举例推导dp数组

//先物品后背包 class Solution {public int change(int amount, int[] coins) {int n = coins.length;int[] dp = new int[amount + 1];Arrays.fill(dp, 0);dp[0] = 1;for (int i = 0; i < n; i++) {for(int j = coins[i]; j<=amount;j++){dp[j] += dp[j-coins[i]];}}return dp[amount];}}

377. 组合总和 Ⅳ  

本题题目描述说是求组合，但又说是可以元素相同顺序不同的组合算两个组合，其实就是求排列！

组合不强调顺序，(1,5)和(5,1)是同一个组合。

排列强调顺序，(1,5)和(5,1)是两个不同的排列。

动规五部曲

1.确定dp数组以及下标的含义

dp[i]: 凑成目标正整数为i的排列个数为dp[i]

2.确定递推公式

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

3.dp数组如何初始化

因为递推公式dp[i] += dp[i - nums[j]]的缘故，dp[0]要初始化为1，这样递归其他dp[i]的时候才会有数值基础。

至于dp[0] = 1 有没有意义呢？

其实没有意义，所以我也不去强行解释它的意义了，因为题目中也说了：给定目标值是正整数！ 所以dp[0] = 1是没有意义的，仅仅是为了推导递推公式。

至于非0下标的dp[i]应该初始为多少呢？

初始化为0，这样才不会影响dp[i]累加所有的dp[i - nums[j]]。

4.确定遍历顺序

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

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

5.举例来推导dp数组

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

二维解法

public class ALL {public static void main(String[] args) {int[] coins = new int[]{1, 2, 5};int amount = 5;int result = change(5, coins);System.out.println(result);}public static int change(int amount, int[] coins) {int[][] dp = new int[amount + 1][coins.length+1];dp[0][0] = 1;// weight数组的大小 就是物品个数for (int i = 1; i <= amount; i++) { // 遍历背包容量for (int j = 1; j <= coins.length; j++) { // 遍历物品,统一下标if (coins[j - 1] <= i) { //保证背包容量比物品容量大for (int k = 0; k <= coins.length; k++) {            //对列进行操作  找出满足某一个背包容量的“组合数”有多少dp[i][j] += dp[i - coins[j-1]][k];}}}}int res = 0;for (int i = 0; i <= coins.length; i++) {  /最后对满足背包容量的所有组合加起来即为排列res += dp[amount][i];}return res;}}