二维费用背包

问题

---

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

过程

---

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

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

实现

---

三维数组

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

二维滚动数组

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