完全背包

问题

---

给定$n$个物品和一个容量为$W$的背包，对于第$i$个物品有重量$w[i]$和价值$v[i]$，且每个物品有无限个可以被选取。选择若干个物品放入背包中，在不超过背包最大容量的情况下，求背包中物品价值之和的最大值。

过程

---

设$dp[i][j]$为前$i$个物品在背包容量为$j$的情况下所能达到的最大总价值。
对于当前第$i$个物品和背包容量$j$，我们有：

• 如果选择第$i$个物品，则$dp[i][j]=dp[i][j-w[i]]+v[i]$。
• 如果不选择第$i$个物品，则$dp[i][i]=dp[i-1][j]$。
  因此$j<w[i]$时有
  $dp[i][j]=dp[i-1][j]$
  $j>=w[i]$时有$dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i])$滚动数组优化：注意到$dp[i][]$只需要$dp[i][]$和$dp[i-1][]$，因此可以去掉第一维并不断更新自身实现空间。

实现

---

二维数组

int N, M;
int n, W;
int w[N], v[N];
int dp[N][M];
 
void knapspack()
{
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= W; j++)
			if(j < w[i])
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = std::max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
}

一维滚动数组

int N, M;
int n, W;
int w[N], v[N];
int dp[M];
 
void knapspack()
{
	for(int i = 1; i <= n; i++)
		for(int j = w[i]; j <= W; j++)
			dp[i][j] = std::max(dp[i][j], dp[i][j - w[i]] + v[i]);
}

题目

---

322. 零钱兑换
518. 零钱兑换 II