完全背包问题

一、什么是完全背包？

        完全背包与01背包问题的区别就在于，01背包中的每种物品只有一个，要么取要么不取，但完全背包中每种物品有无限个，可以取多次。

        注：文章内容是我二刷代码随想录之后的总结，侧重点是不同类型题的代码该如何书写，还有一维dp数组和二维dp数组如何使用以及一些学习中遇到的细节问题。不了解01背包的读者也可以看我写的01背包问题。

二、完全背包题型

（一）题型一：求ture or false

        刷代码随想录“完全背包”模块的过程中这种类型我只看到了一题，即已知字符串s，和一个字符串集合wordDict，让我们判断利用集合中的字符串，可不可以组成字符串s，集合中的字符串可以重复使用。我感觉这种题型与下面的题型二是差不多的，这里的字符串s就相当于背包，wordDict中的字符串就相当于物品。当然还有不同的是这种题型中dp数组的值是boolean类型的，所以我就给他取名为“求true or false”。力扣139.单词拆分

卡哥动规五部曲：

dp数组含义dp[i]:使用字典中的单词，能否组成字符串s，0-(i-1)的子串

递推公式：从字典中选取一个单词，长度为len, 如果dp[i-len]=true;并且s.substring(i - len, i).equals(word)，则dp[i]=true;

初始化：长度为0的子串，不选单词的情况下可以组成，所以dp[0]=true;

遍历顺序：从前到后

打印dp数组

class Solution {public boolean wordBreak(String s, List<String> wordDict) {int size = wordDict.size();int length = s.length();boolean[] dp = new boolean[length + 1];dp[0] = true;//内外循环不可以对换for(int i = 1; i <= length; i++){for(String word : wordDict){int len = word.length();if(i >= len && dp[i - len] && s.substring(i - len, i).equals(word)){dp[i] = true;}}}return dp[length];}
}

（二）题型二：求最值

        题干模型：有n类物品，每类物品有无限个，已知它们的重量和价值，问我们容量为W的背包可以装下物品的最大价值。这里我们假设物品i的重量为weight[i]，价值为value[i]，背包容量为W。以卡码网52. 携带研究材料为例：

卡个动规五部曲：

dp数组含义：dp[i][j]使用前i个物品，背包容量为j时，能装入物品的最大价值

递推公式：当背包容量j>weight[i-1]时，我们可以选择装入weigth[i-1],也可以不装入，而我们要求最大值，所以选择价值较大的最大的max(dp[i-1][j], dp[i][j-weight[i-1]]+value[i-1]);当背包容量j<weight[i-1]是，我们不可以装入weight[i-1]所以，dp[i][j] = dp[i-1][j]

初始化：当背包容量为0时，最大价值均为0，所以dp[i][0]=0,当使用前0个物品转入背包式，最大价值也为0，所以dp[0][j]=0;

遍历顺序：从前向后，从上到下

打印dp数组

使用二维dp数组：

import java.util.Scanner;public class Main{public static void main(String[] args){Scanner scan = new Scanner(System.in);int N = scan.nextInt();//物品种类数int W = scan.nextInt();//背包容量int[] value = new int[N];//用来存储物品价值int[] weight = new int[N];//用来存储物品质量for(int i = 0; i < N; i++){//初始化weight[i] = scan.nextInt();value[i] = scan.nextInt();}int[][] dp = new int[N+1][W+1];//内层与外层循环可以对换for(int i = 1; i <= N; i++){for(int j = 0; j <= W; j++){if(j >= weight[i-1]){dp[i][j] = Math.max(dp[i-1][j], dp[i][j-weight[i-1]]+value[i-1]);}else{dp[i][j] = dp[i-1][j];}}}System.out.print(dp[N][W]);}
}

使用一维dp数组：

import java.util.Scanner;
public class Main{public static void main(String[] args){Scanner scan = new Scanner(System.in);int N = scan.nextInt();//物品种类数int W = scan.nextInt();//背包容量int[] value = new int[N];//用来存储物品价值int[] weight = new int[N];//用来存储物品质量for(int i = 0; i < N; i++){//初始化weight[i] = scan.nextInt();value[i] = scan.nextInt();}int[] dp = new int[W+1];//内层与外层循环可以对换for(int j = 0; j <= W; j++){for(int i = 0; i < N; i++){if(j>=weight[i]){dp[j] = Math.max(dp[j - weight[i]] + value[i], dp[j]);}}}System.out.print(dp[W]);}
}

上面的两种形式都是先遍历物品后遍历背包，其是也可以先遍历背包在遍历物品。（解释在最下边）

（三）题型三：求组合数

        有n类物品，每类物品有无限个，已知它们的重量和价值，问我们装满容量为W的背包有多少种装法。假设第i个物品的重量为weight[i].以力扣518.零钱兑换为例。

按照卡哥教的动规五部曲：

dp含义：dp[i][j]表示使用0-i个物品，凑成金额j有几种组合方法
递推公式：dp[i][j] = j >= coins[i]？dp[i - 1][j] : dp[i - 1][j] + dp[i][j - coins[i]];

遍历顺序：从前到后，从左到右
初始化：

        // 初始化第一列
        for (int i = 0; i < coins.length; i++) {
            dp[i][0] = 1;
        }

        // 初始化第一行
        for (int i = coins[0]; i <= amount; i++) {
            dp[0][i] += dp[0][i - coins[0]];
        }

打印dp数组

使用二维dp数组：

class Solution {public int change(int amount, int[] coins) {int[][] dp = new int[coins.length][amount + 1];// 初始化第一列for (int i = 0; i < coins.length; i++) {dp[i][0] = 1;}// 初始化第一行for (int i = coins[0]; i <= amount; i++) {dp[0][i] += dp[0][i - coins[0]];}//(也可以先遍历背包，再遍历物品）for (int i = 1; i < coins.length; i++) {for (int j = 1; j <= amount; j++) {dp[i][j] = dp[i - 1][j];if (j >= coins[i]) {dp[i][j] += dp[i][j - coins[i]];}}}return dp[coins.length - 1][amount];}
}

优化使用一维dp数组：

class Solution {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];}
}

      （四）题型四：求排列数

        有n类物品，每类物品有无限个，已知它们的重量和价值，问我们装满容量为X的背包有多少种装法，装入顺序不同也被认为是不同的装法。以力扣377.组合总和IV为例

        这个题的的二维解法可以看这个视频：LeetCode 377 二维dp，但我总感觉这道题二维不如一维简单。

使用二维dp数组：

class Solution {public int combinationSum4(int[] nums, int target) {Arrays.sort(nums);int[][] dp = new int[nums.length + 1][target + 1];for (int i = 0; i <= nums.length; i++) {dp[i][0] = 1;}for (int j = 1; j <= target; j++) {for (int i = 1; i <= nums.length; i++) {if (j >= nums[i - 1]) {for (int k = 0; k < i; k++) {dp[i][j] += dp[i][j - nums[k]];}} else {dp[i][j] = dp[i - 1][j];}}}return dp[nums.length][target];}}

使用一维dp数组：

数组含义：dp[j]使用0-i个数，和为j的的组合数；

class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target + 1];dp[0] = 1;for (int j = 0; j <= target; j++) {for (int i = 0; i < nums.length; i++) {if(j >= nums[i]){dp[j] += dp[j - nums[i]];}}}return dp[target];}
}

细节问题：先遍历背包还是先遍历物品 

        好了,题型已经列举完了,下面我来讲一下题型二、题型三和题型四里的循环顺序（先遍历背包，还是先遍历物品）的问题。

先来看题型三（求组合数）和题型四（求排列数）

        咱们先来讲使用二维dp数组的解法，对于这两种题型，使用二维dp数组时，无论是先遍历背包，还是先遍历物品，都是可以的，那原因是什么呢？如果你观察一下他们的递推关系式，你就可以发现dp[i][j]的值都是由其左上方（在dp数组中的相对位置）的值推出来的，所以我们无论是先遍历背包还是先遍历物品，都可以保证先求出dp[i][j]左上方的值，从而在求出dp[i][j]

        但是，如果你使用的是一维数组的话那可就不一样了，首先指明：

•  求组合数，需要先遍历物品，再遍历背包
•  求排列数，需要先遍历背包，在遍历物品

这又是为什么呢？这是因为求组合数时，{1,2}，{2,1}我们需要当成一种情况处理，如果我们先遍历背包，再遍历物品的话，就会有如下情况：

        当背包容量为x时，我们放入了1，然后当背包容量为y时，我们放入了2；也有可能当背包容量为x时，我们放入了2，然后当背包容量为y时，我们放入了1，总之，在这种遍历顺序的情况下，有可能同时出现{1,2}，{2,1}。

        那先遍历物品就不会出现这种情况吗？答案是不会的，因为先遍历物品时，一个物品只会被遍历一次，物品一只会出现在物品二前面。（所以题型一中我们也要先遍历背包，保证单词出现的顺序可以改变）

        看到这里，可能有人又有疑问了----为什么二维dp可以随意颠倒背包和物品的顺序，而一维的确不行？其实是因为，使用一维dp是空间是共享的，从而到值了这种情况，自己逐步去模拟一下就会发现了。

然后我们来看一下，题型二（求最值）

     求最值的题型中，无论是使用二维dp数组还是使用一维dp数组，我们都不需要考虑是先遍历物品还是先遍历背包。那是为什么呀？读了上面‘求组合数’和‘求排列数’的分析我们可以知道遍历的顺序取决于求排列数，还是求组合数，那我们求最值的时候还需要考虑组合或值排列吗？当然不需要了！{1， 2}和{2， 1}是一种组合，两种排列，但是它们的最值都是相同的。