背包问题——01背包
本文最后更新于404 天前,其中的信息可能已经过时,如有错误请发送邮件到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]]);
	}
}
如果觉得本文对您有所帮助,可以支持下博主,一分也是缘
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
/* */