动态规划背包问题——01背包(超详细)

  • 时间:
  • 来源:互联网

01背包问题

问题背景:
设有容量为V的背包,有N种物品,每件物品的体积是c[i],对应的价值是v[i],每种物品只有一个,要使背包中所装物品的价值总和最大,问该如何选择。
用一个二维数组f[i][j],来表示i件物品,在用j的容量时的最大的价值。因为对于每一件物品,你选择就只能是装或者不装这件物品。
例如:
物品: a b c d
体积: 5 4 6 10
价值; 10 7 14 25
当你背包装1件物品时,假如你的背包容量为4,此时f[1][4]=7,你只能装物品b,如果你背包容量为9,这时你就有了选择,能够装下物品a,b,c中的任何一个,因为只能装下一件物品,所以即使你能装下a和b,你当然也只能选价值最大的物品c,即f[1][9]=14。
第一件物品当然是比较简单,当背包装两件物品时(i=2),当你背包还能装下第二件物品,此时你有两个选择,对第二件物品拿与不拿:
拿的话就是f[i][j] = f[i-1][j – c[i]] + v[i] 下划线部分是拿第i个物品之前最多能拿的价值,再加上v[i](第i个物品的价值)这就是拿第i个物品时的最大价值。
不拿的话就是f[i][j] = f[i-1][j]就相当于装i-1件物品的最大价值。当你背包装不下第二件物品的时候也是f[i][j] = f[i-1][j](装不下了,还不是只能像前面一样呗)
这时,我们每一步都是取的最佳方案(得到了最大价值)
我们就可以得出状态转移方程 f[i][j] = max(f[i-1][j], f[i-1][j – c[i]] + v[i])
目标就是f[N][V]

这里有个难理解的地方就是初学者可能认为,f[i][j] = f[i-1][j – c[i]] + v[i]不是装得下就装了吗?
并不是这样!!! 当你的背包容量V = 26时
我们不如打个表看看在这里插入图片描述

比如f[3][25] = max(f[2][25], f[2][25-6] + 14) = max(39, 56)=56 这就不对了 为什么呢?!
比如f[4][25] = max(f[3][25], f[3][25-10] + 25) = max(49,56)=56; 这又是对的
但是!!! 程序出来是这样的在这里插入图片描述

在这里
比如f[3][25] = max(f[2][25], f[2][25-6] + 14) = max(17, 31)=31
比如f[4][25] = max(f[3][25], f[3][25-10] + 25) = max(31,56)=56;
这才是正解(为什么会这样的原因,相信读者能自己分析出来)
有没有发现,只有最后一行代码才有用,这时我们想到了用一维数组来优化。

先写出状态转移方程f[j] = max(f[j], f[j – c[i]] + v[i])

我们可以继续分析一波数据
还是用上面的例子:
物品: a b c
体积: 5 4 6
价值; 10 7 14

当 i = 1 时
f[0] 到 f[4]显然都是零
f[5] = max(f[5], f[0] + 10)= 10
f[6] = max(f[6], f[1] + 10) = 10

f[9] = max(f[9], f[4] + 10) = 10
f[10] = max(f[10], f[5] + 10)=20
!!! 问题出现了,如果每件物品只拿一次,价值不可能出现20
仔细分析发现原来是物品a拿了两次既f[10]不仅由f[5]决定了而且还被f[0]影响了,这显然是不对的,这就是我们后面要讲的完全背包问题。
我们想出了一个解决办法,不是f[10]被前面多次刷新嘛,我们第二层循环倒着来。J=14开始(我们不分析这么多了背包就取14)到j>=c[i]就可以了,因为前面都是0,没有意义。
i = 1时
f[14] = max(f[14], f[9] + 10) = 10
f[13] = max(f[13], f[8] + 10) = 10

f[5] = max(f[5], f[0] + 10) = 10
i = 2时
f[14] = max(f[14], f[10] + 7) = 17

f[9] = max(f[9], f[5] + 7) = 17
f[8] = max(f[8], f[4] + 7) = 10;
看到没,f[9]到f[14]的值刷新了
i = 3 时
f[14] = max(f[14, f[8] + 14] = 24
f[13] = max(f[13], f[7] +14) = 24

后面就不列举了,我们要的结果f[14]已经出来了显然这是正确的答案。
由此可见对于二维数组,我们可以用一维滚动数组来实现,减少不必要的浪费。
重点来了!!!用滚动数组的时候内层循环一定要逆序

再写一点关于初始化的问题,对于背包问题,有要求背包装满与不装满两种情况
  1. 装满那就要f[0] = 0; 其他的都为-∞,为什么呢,因为只有在背包容量为0的时候才可以一个都不装价值为0,当背包有容量,就可能装得下东西,但你不能选择什么都不装对吧,这不符合要求,所以初始化为-∞之后,只有当你装之后这个值才有意义。
  2. 不要求装满就全部初始化为0,理由同上,装与不装是你的选择,你可以留着容量不装,这时所有值都有意义。
    最后贴上01背包的代码
    二维:
for(int i = 1; i <= N; i++)//N表示种类
	for(int j = 1; j <= V; j++)//V表示背包容量 这里循环正序逆序都行 
	if(j >= c[i])
	f[i][j] = max(f[i-1][j], f[i-1][j - c[i]] + v[i]) 
	else
	f[i][j] = f[i-1][j]
	cout << f[N][V];

滚动数组:

for(int i = 1; i <= N; i++)
	for(int j = V; j >= c[i]; j--)// 一定要逆序 
	f[j] = max(f[j], f[j - c[i]] + v[i]);
	cout << f[V];
注:此文章问原创,开源,可转载但请注明出处!
yezi_coder
发布了2 篇原创文章 · 获赞 0 · 访问量 3
私信 关注

本文链接http://element-ui.cn/news/show-914.aspx