算法 DAY44 动态规划6 完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法 DAY44 动态规划6 完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

完全背包

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
算法 DAY44 动态规划6 完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ

void test_CompletePack() {
		vector<int> weight = {1, 3, 4};
		vector<int> value = {15, 20, 30};
		int bagWeight = 4;
		vector<int> dp(bagWeight + 1, 0);
		for (int j = 0; j <= bagWeight; ++j) {
			for (int i = 0; i < weight.size(); ++i) {
				if (j >= weight[i]) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
			}
		}
		cout << dp[bagWeight];
	}

518. 零钱兑换 II

动规五步曲来分析如下：

1、确定dp数组以及下标的含义
dp[j]：凑成总金额j的货币组合数为dp[j]

2、确定递推公式
dp[j] 就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加。
所以递推公式：dp[j] += dp[j - coins[i]];

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

4、遍历顺序
如果背包容量在外层，物品在内层：

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，2，5} ，目标和是5
当背包容量为4，此时遍历物品，j不变，变动i，实现连加。
那么 dp[3] = dp[2] + dp[1]
dp[4]：有硬币1时，有dp[2]种可能，有硬币2时，有dp[1]种可能，5>4，没可能，所以5不参与连加。但是此时会有个问题：dp[2]:{1,1},{2}，dp[1]:{1}。于是dp[3] : {{1,1,1}，{2,1}} {1,2} 很明显{1，2}这个组合重复了。

所以正确的遍历方式应该是先遍历物品，内层遍历背包容量：
以下遍历方式就不会出现重复组合

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

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

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1,0);
        int count = 0;
        dp[0] = 1;
        for(int i = 0; i < coins.size(); ++i){
            for(int j = coins[i]; j <= amount; ++j){
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};

377. 组合总和 Ⅳ

本质是完全背包求排列问题文章来源地址https://www.toymoban.com/news/detail-430196.html

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