完全背包理论

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

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

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

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

1
2
3
4
5
6
7
// 先遍历物品，再遍历背包
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]);

    }
}
1
2
3
4
5
6
7
/ 先遍历背包，再遍历物品
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]);
    }
    cout << endl;
}

纯完全背包 是凑成背包价值最大是多少。

518.零钱兑换II

文章：19. 零钱兑换II

题目：518. 零钱兑换 II

【思路】

钱币不限，完全背包问题。

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

组合数！ 而不是排列数。（去重）

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

1.确定数组及其下标含义

dp[j]：凑成总金额j的货币组合个数为dp[j]（金额是背包，货币是物品）

2.确定递推公式

dp[j] 就是所有dp[j-coins[i]]的相加

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

3.dp数组如何初始化

dp[0]一定要是1，是累加递归的基础。

4.确定遍历顺序

本题求的是组合数，对排列的顺序要求是去重，因此需要规定for循环的先后顺序。

物品在外边：物品只遍历一次，不重复遍历（组合数）

背包在外面：物品多次遍历（排列数）

5.举例推导。。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int change(int amount, int[] coins) {
        //题目提到：每一种面额的硬币有无限个： 完全背包
        //并且，dp[i] 会依赖于dp[i-coins[j]]的累加
        //1.确定dp及其下标的含义 : dp[j] 为下标为j时dp[j]为凑到j金额的最大硬币数
        int[]dp = new int[amount + 1];
        //3.初始化数组
        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];
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
func change(amount int, coins []int) int {
    dp := make([]int,amount+1)
    dp[0]=1
    for i:=0;i<len(coins);i++{
        for j:=coins[i] ;j <= amount;j++{
            dp[j] += dp[j-coins[i]]
        }
    }
    return dp[amount]
}

377.组合总和IV

文章：21. 组合总和Ⅳ

题目：377. 组合总和 Ⅳ

【思路】

本题提到找出和为给定目标正整数的组合的个数。而给的样例是顺序不同视作不同的组合，其实求的是排列数。

这题就是和上题差不多，求的是排列数，换一下背包和物品的遍历顺序以及改一下变量就好噜。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int combinationSum4(int[] nums, int target) {
        //数字可以重复出现：完全背包
        //需要累加
        //1.确认dp数组及其下标含义 ： dp[j]为下标为j时，dp[j]为最大组合数
        
        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] >=0 )dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
func combinationSum4(nums []int, target int) int {
    dp := make([]int,target+1)
    dp[0]=1
    for i:=0;i<=target;i++{
        for j := 0;j<len(nums);j++{
            if i - nums[j] >= 0{
                dp[i] += dp[i-nums[j]]
            }
        }
    }
    return dp[target]
}

【算法总结】

  • 零钱兑换II：因为零钱的数量是无限的，因此采用完全背包。题目示例提出求的是组合数（去重），因此采用物品在外循环，背包在内循环，这样保证了物品只被循环一次。
  • 组合总和IV：因为数字的个数是无限的，因此采用完全背包。题目示例提出求的是排列数（不同的排列均算入答案），因此采用背包在外循环，物品在内循环，这样保证了物品会被多次循环。