本文最后更新于542 天前,其中的信息可能已经过时,如有错误请发送邮件到1739584917@qq.com
题目
最基本的背包问题就是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]]);
}
}