# 题目

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

# 分析

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

01 背包和完全背包唯一不同就是体现在遍历顺序上

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

	for(int i = 0; i < weight.size(); i++) { // 遍历物品
	for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
	dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
	}
	}

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

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

	// 先遍历物品，再遍历背包
	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]);

	}
	}

完整代码

	// 先遍历物品，在遍历背包
	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 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]);
	}
	}
	cout << dp[bagWeight] << endl;
	}
	int main() {
	test_CompletePack();
	}

	// 先遍历背包，再遍历物品
	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] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
	}
	}
	cout << dp[bagWeight] << endl;
	}
	int main() {
	test_CompletePack();
	}

动态规划