题目

最基本的背包问题就是01背包问题（01 knapsack problem）：一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？

分析

对于每件物品，我们都有取和不取两种两种情况，所以我们定义状态dp：

dp[i][j]//表示只考虑前i件物体、体积为j的情况下背包的最大价值

我们将dp[0][0…w]初始化为0，因为这表示的是考虑前0件物品的情况下背包的最大价值，没有物品，也就没有价值；

同样将dp[0…n][0]初始化为0，表示的是考虑体积为0的情况下背包的最大价值，没有体积，同样没有价值；

那么当i>0时，dp[i][j]有两种情况：

• 装入第i件物品：dp[i][j]=v[i]+dp[i-1][j-w[i]]; //j-w[i]指装完第i件物品后剩余体积
• 不装入第i件物品：dp[i][j]=dp[i-1][j];

所以状态转移方程为：

dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]]+v[i]) // j >= w[i]

核心代码：

for (int i=1;i<=N;i++)
	{
		for (int j=0;j<=W;j++)
		{
			if (j>=w[i])
			{
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}
		}
	}

优化

我们可以发现，当我们循环i件物品时，并不会用到i-2件物品时的数据;

并且如果我们j从大到小循环时，也不会用到dp[i][j……]之后的数据

所以我们可以去掉一维：

dp[i]=max(dp[i],dp[j-w[i]]);//j>=w[i]时

当我们循环到dp[i]时,只要还没执行状态转移方程，那么当前的dp[i]及(dp[……i])之前的数据都是i-1件物品时的数据;代码也就变成了这样：

for (int i = 1; i <= N; i++)
{
	for (int j = W; j >= 0; j--)
	{
		if (j >= w[i])
		{
			dp[i]=max(dp[i],dp[j-w[i]]);
		}
		else
		{
			dp[j] = dp[j];
		}
	}
}
//完全等价于二维的

很明显，dp[j]==dp[j]显然是没有意义的，并且w[i]>0;所以代码优化成下面的样子：

for (int i = 1; i <= N; i++)
{
	for (int j = W; j >= w[i]; j--)
	{
		dp[j]=max(dp[j],dp[j-w[i]]);
	}
}