0-1背包

问题

---

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

样例

---

输入：
3 4
4 1
5 2
1 5
输出：
3 （只选3）

过程

---

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

• 如果选择第$i$个物品，则$dp[i][j]=dp[i-1][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 - 1][j - w[i]] + v[i])$$

滚动数组优化：注意到$dp[i][]$只需要$dp[i][]$和$dp[i-1][]$，因此可以去掉第一维并不断更新自身实现空间。

遍历顺序

与二维$dp[][]$从小到大$0$到$W-w[i]$不同，滚动数组$dp[]$需要从大到小$W-w[i]$到$0$来确保每个物品只会被选择一次。

实现

---

二维数组

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 - 1][j - w[i]] + v[i]);
}

一维滚动数组

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