算法日记-02完全背包和多重背包问题总结

完全背包问题总结

完全背包问题-有N件物品和一个最多能背重量为W的背包

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

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

在下面的讲解中，我依然举这个例子：

背包最大重量为4。

物品为：

每件商品都有无限个！

问背包能背的物品最大价值是多少？

解题思路

首先再回顾一下01背包的核心代码

01背包二维递推公式

//递推公式
dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
//其中dp[i][j]表示当前可装入0-i物品 背包容量为j的背包装入的最大价值
1
2
3

01背包一维递推公式

//递推公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
//我们使用滚动数组进行动态压缩后可得以上递推公式
1
2
3

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

所以其实完全背包问题的一二维递推表达式和01背包问题相同，而完全背包的物品是可以添加多次的

所以要从小到大去遍历，即：

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

解题模板

//先遍历物品，再遍历背包
private static void testCompletePack(){
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagWeight = 4;
    int[] dp = new int[bagWeight + 1];
    for (int i = 0; i < weight.length; i++){ // 遍历物品
        for (int j = weight[i]; j <= bagWeight; j++){ // 遍历背包容量
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    for (int maxValue : dp){
        System.out.println(maxValue + "   ");
    }
}

//先遍历背包，再遍历物品
private static void testCompletePackAnotherWay(){
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagWeight = 4;
    int[] dp = new int[bagWeight + 1];
    for (int i = 1; i <= bagWeight; i++){ // 遍历背包容量
        for (int j = 0; j < weight.length; j++){ // 遍历物品
            if (i - weight[j] >= 0){
                dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
            }
        }
    }
    for (int maxValue : dp){
        System.out.println(maxValue + "   ");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

经典例题

力扣322.零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
1
2
3

示例 2：

输入：coins = [2], amount = 3
输出：-1
1
2

示例 3：

输入：coins = [1], amount = 0
输出：0
1
2

代码实现：

class Solution {
    public int coinChange(int[] coins, int amount) {
        //定义dp数组  dp[i]表示凑成金额为i的硬币所需的最少硬币个数
        int[] dp = new int[amount+1];
        int max = Integer.MAX_VALUE-1;
        //初始化dp数组
        for (int j = 0; j < dp.length; j++) {
            dp[j] = max;
        }
        dp[0] = 0;
        //因为是要找出最少的次数所以 遍历顺序不影响
        for(int i=0;i<coins.length;i++){
            for(int j=0;j<amount+1;j++){
                //当背包容量大于等于硬币i的价值时 才能放入
                if(j>=coins[i]){
      				//dp[j-coins[i]]表示当放入硬币i时剩余背包装满所需的最少硬币个数
                    dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }
        if(dp[amount]==max||dp[amount]<0){
            return -1;
        }
        return dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

力扣518.零钱兑换II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
1
2
3
4
5
6
7

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
1
2
3

示例 3：

输入：amount = 10, coins = [10] 
输出：1
1
2

实现代码：

class Solution {
    public int change(int amount, int[] coins) {
        int count = 0;
        //定义dp数组
        int[] dp = new int[amount+1];
        //这里初始化为1是方便后续计算 因为能装满背包的话 恰好得到dp[0] 这时我们需要让对应的dp[j]=1
        dp[0] = 1;
        //先遍历物品
        for(int i=0;i<coins.length;i++){
            //在遍历容量 j=coins[i]是因为 当背包容量大于等于硬币价值时才能放入
            for(int j=coins[i];j<amount+1;j++){
                //先固定拿物品i 然后放入背包中 就能到有多少种放满背包的方式了
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

力扣377.组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
1
2
3
4
5
6
7
8
9
10
11
12

示例 2：

输入：nums = [9], target = 3
输出：0
1
2

实现代码：

class Solution {
    public int combinationSum4(int[] nums, int target) {
        //定义dp数组  dp[i] 表示总和为i一共有dp[i]种方法
        int[] dp = new int[target+1];
        //初始化dp数组
        dp[0] = 1;
        //因为本题强调了结果的排序性 所以我们先遍历背包在遍历物品求排列
        //先遍历背包
        for(int i=0;i<target+1;i++){
            //在遍历物品
            for(int j=0;j<nums.length;j++){
                if(i>=nums[j]){
                    //dp[1] = 1   dp[2] = 2 
                    dp[i] += dp[i-nums[j]];
                }
            }
        }        
        for(int i=0;i<dp.length;i++){
            System.out.print(dp[i]);
        }
        return dp[target];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

力扣279.完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4
1
2
3

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9
1
2
3

代码实现：

class Solution {
    public int numSquares(int n) {
        //定义dp数组 dp[i] 表示返回和为i的最少数量
        int[] dp = new int[n+1];
        //初始化dp数组
        int max = Integer.MAX_VALUE;
        for(int i=0;i<dp.length;i++){
            dp[i] = max;
        }
        dp[0] = 0;
        //遍历dp数组 因为题目强调的是求最少数量 因此遍历顺序都可
        //先遍历金额
        for(int i=1;i*i<=n;i++){
            //在遍历背包  为什么j=i*i 
            //是因为如果j
            for(int j=i*i;j<n+1;j++){
                //只有当放入这个数后剩余背包能放下的数量不为max才有意义 不然无法组成n
                if(dp[j-i*i]!=max){
                    dp[j] = Math.min(dp[j],dp[j-i*i]+1);
                }
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

力扣139.单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
1
2
3

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。
1
2
3
4

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
1
2

实现方法：

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //定义dp数组 dp[i]表示从0-i区间的满不满足条件 若满足条件设为true不满足为false
        boolean[] dp = new boolean[s.length()+1];
        //利用hashset来去重
        HashSet<String> set = new HashSet<>(wordDict);
        //初始化dp数组
        dp[0] = true;
        //遍历
        for(int i=0;i<s.length()+1;i++){
            for(int j=0;j<i;j++){
                //如果截取下来的字符串能匹配到 并且他截取之前的串也满足条件 那么他们俩都满足条件
                if(set.contains(s.substring(j,i)) && dp[j]){
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

小结

零钱兑换问题中，要求出装满背包所需的最少硬币个数，装不满则返回-1

首先考虑，要当背包容量即总金额大于硬币价值我们才能进行兑换

在这道题中值得留意的是，我们每放入一个硬币则需要让dp数组值+1 而不是以往的加入硬币价值

零钱兑换II，组合总和问题中，就是给你一堆零钱（零钱个数无限），为凑成amount的组合数有几种。

注意这里组合数和排列数的区别！（排列强调顺序性，组合不强调）

这里在遍历顺序上可就有说法了。

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

完全平方数这道题求的是给定正整数 n，找到若干个完全平方数使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

所以类似于零钱兑换II问题，不过这次我们不是放的硬币价值了 而是放的硬币价值的平方，将递推式稍微修改即可

单词拆分这道题我们要想到本题其实我们求的是排列数，为什么呢？

拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 举例。

“apple”, “pen” 是物品，那么我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。

“apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的，那么我们就是强调物品之间顺序。

所以说，本题一定是 先遍历 背包，再遍历物品

其中一定要深刻理解dp[i]表示的是截取s字符串0-i区间是否可以组成，在此基础上我们在判断新截取的那个字符我们能否在set集合中找到

多重背包问题

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

多重背包和01背包是非常像的， 为什么和01背包像呢？

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

例如：

背包最大重量为10。

物品为：

问背包能背的物品最大价值是多少？

和如下情况有区别么？

毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。

    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int[] nums = {1,2,2};
        int bagWight = 4;
        testWeightBagProblem(weight, value, bagWight);
    }

    public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
        int wLen = weight.length;
        //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
        int[] dp = new int[bagWeight + 1];
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 0; i < wLen; i++){
            //这里注意 使用一维数组解决01背包问题 背包大小需要倒序遍历以避免重复获取物品
            for (int j = bagWeight; j >= weight[i]; j--){
                //这里遍历物品的数量 是把多重背包问题转化为01背包的关键
            	for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数
                	dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
            	}
            }
        }
        //打印dp数组
        for (int j = 0; j <= bagWeight; j++){
            System.out.print(dp[j] + " ");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

从代码里可以看出是01背包里面在加一个for循环遍历一个每种商品的数量。 和01背包还是如出一辙的。