代码随想录算法训练营第44天 | 完全背包理论基础 518.零钱兑换II 377.组合总和 Ⅳ

完全背包理论基础

完全背包与01背包只相差在物品是无限取用的。因此和01背包相比第二层对背包容量的遍历应该是正序的，而且正因为这个正序，使得在纯完全背包问题中，背包容量和物品的遍历是可以倒过来的。

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, bagSize;
	cin >> n >> bagSize;
	vector<int> weight(n, 0);
	vector<int> value(n, 0);
	for(int i = 0; i < n; i++) {
		cin >> weight[i] >> value[i];
	}
	vector<int> dp(bagSize + 1, 0);
	for(int i = 0; i < n; i++) {
		for(int j = weight[i]; j <= bagSize; j++) {
			dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
		}
	}
	cout << dp[bagSize] << endl;
	return 0;
}

零钱兑换II

这道题递推式和目标和那道题是一致的，都是解决装满背包的方法数目问题。重点在于遍历顺序，我们前面总结过对于纯完全背包问题，先遍历背包还是先遍历物品都是一样的。
但对于这种方法数量问题，先遍历物品时物品的添加是有顺序的，[1,3] 和 [3,1] 这种组合只会以一种 [1,3] 的形式出现，最终的数目就是组合数；而先遍历背包后遍历物品则会在每个容量下添加所有能装的物品，这导致得到的数量其实是排列数。

class Solution{
public:
	int change(int amount, vector<int>& coins) {
		vector<int> dp(amount + 1, 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];
	}
};

组合总和IV

这道题对应了前面说的排列数目，需要先遍历背包，再遍历物品。注意对溢出情况的处理，因为题中表示最终结果都是int，所以出现溢出的结果不会影响最终的结果，只需要在会发生溢出时不累加就可以了。

class Solution{
public:
	int combinationSum4(vector<int>& nums, int target) {
		vector<int> dp(target + 1, 0);
		dp[0] = 1;
		for(int j = 1; 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];
	}
};