0-1 背包算法:每个物品只有一件,放入背包中; V(80), W(60) V(50), W(50) V(50), W(50) 总重量 100 按照贪心算法放第一个,但实际取第二,第三个为最优;
一般背包算法:每个物品多件,放入背包中; V(80), W(60) V(50), W(50) V(50), W(50) 总重量 100 按照贪心算法也只能放第一个,同样也不适用贪心算法?
问题:一般背包是说物品有多件还是一件物品,可以取部分?
1
DaCong 2017-11-11 15:24:42 +08:00 via Android
先回答问题,是指一个物品有多件
如果楼主想要深入学习背包的话,我这里收集过一个比较好的讲解,楼主可以参考一下 https://github.com/tianyicui/pack/blob/master/V2.pdf |
2
zhangwugui OP @DaCong 嗯,好的。我记得贪心算法应该是可以适用于一般背包算法的呢。那按照上面的来说,贪心算法不适用么?我先去看看这个 PDF。
|
3
zhangwugui OP 我是在学习贪心算法的时候,看到贪心算法适用一般背包问题,而没搞明白的。
|
4
DaCong 2017-11-11 15:41:49 +08:00
@zhangwugui #2 你的一般背包问题的定义是怎样的?
是不是"有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 M i 件可用,每件耗费的空间是 C i ,价值是 W i。"? 如果是的话,那么很显然不能贪心,看 PDF 中的多重背包就可以了。 |
5
DaCong 2017-11-11 15:44:48 +08:00 1
@zhangwugui #3 就看那个人对于一般背包的定义了,在我看来,背包问题,就要保证物品不可分割。如果所谓的“一般背包”是可以分割物品的,那就可以贪心(算单位体积的价值,取最大)。
|
6
zqqian 2017-11-11 15:47:52 +08:00 via Android
可以去看看背包九讲
|
7
zhangwugui OP @DaCong 嗯,对于一般背包我是这样理解的:有 N 件物品和一个最大重量为 V 的背包,其中每件物品有多个,每件背包重量为 W(i),每件物品价值为 P(i),在保证不超过最大重量 V 的情况下,放入的物品价值最大?
因为我现在学的贪心算法,也看了看网上说的,贪心算法可以解决这个问题,就使用贪心算法: 依次取 价值除以重量 P(i)/W(i) 最大的放进去就行,但实际上这确实不行的。不知道这种情况算一般算法不,还是我说的这个贪心策略不对。 |
8
DaCong 2017-11-11 16:06:08 +08:00
@zhangwugui #7 多个是指没有上限吗?如果是的话,就是完全背包问题,我给你的链接里有讲到
我给你的 PDF 就是 6# 说的背包九讲 |
9
zjsxwc 2017-11-11 16:36:54 +08:00 via Android
mark 下, 动态规划主要就是状态转移方程。
我记得背包问题在那个讲解图里面: 01 背包是 斜、 竖 方向的 转移 完全背包是 横、 竖 方向的 转移 |
10
xupefei 2017-11-11 17:26:07 +08:00 1
可以放无限次的叫 unbounded knapsack,放一次的叫 0/1 knapsack,可拆分的叫 fractional knapsack。
没有“一般背包”这种说法。 0/1 背包用贪心算法能保证 50%最优解。 fractional knapsack 的贪心算法可以保证最优解:通过事先按照 value/weight 比值排序后逐个选取。 |
12
zhangwugui OP @DaCong 嗯嗯,感谢。大概明白了,我可能太纠结在贪心算法了。去学习学习动态规划。
|
13
zhangwugui OP @xupefei 嗯,多谢指导,明白了。我所说的那种应该就是 unbounded knapsack。
|
14
nicoley 2017-11-11 23:32:41 +08:00
@zjsxwc 动态规划我个人感觉它就三部曲,状态的定义,状态如何转移,再就是一些边界条件。。而不是你所说的主要是状态转移。。。。(个人愚见,请大家多多指教
|
15
jedihy 2017-11-12 08:24:09 +08:00
@zhangwugui 面试极少会考到,不是个人兴趣没必要太深究了。
|
16
zhangwugui OP @jedihy 嗯,最近回过头来看算法的时候,又看到了,再了解下。
|