有点不太清楚 一般背包算法？

[zhangwugui]

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 按照贪心算法也只能放第一个，同样也不适用贪心算法？

问题：一般背包是说物品有多件还是一件物品，可以取部分？

[DaCong]

先回答问题，是指一个物品有多件
如果楼主想要深入学习背包的话，我这里收集过一个比较好的讲解，楼主可以参考一下

https://github.com/tianyicui/pack/blob/master/V2.pdf

[zhangwugui]

@DaCong 嗯，好的。我记得贪心算法应该是可以适用于一般背包算法的呢。那按照上面的来说，贪心算法不适用么？我先去看看这个 PDF。

[zhangwugui]

我是在学习贪心算法的时候，看到贪心算法适用一般背包问题，而没搞明白的。

[DaCong]

@zhangwugui #2 你的一般背包问题的定义是怎样的？
是不是"有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 M i 件可用,每件耗费的空间是 C i ,价值是 W i。"？
如果是的话，那么很显然不能贪心，看 PDF 中的多重背包就可以了。

[DaCong]

@zhangwugui #3 就看那个人对于一般背包的定义了，在我看来，背包问题，就要保证物品不可分割。如果所谓的“一般背包”是可以分割物品的，那就可以贪心（算单位体积的价值，取最大）。

[zqqian]

可以去看看背包九讲

[zhangwugui]

@DaCong 嗯，对于一般背包我是这样理解的：有 N 件物品和一个最大重量为 V 的背包，其中每件物品有多个，每件背包重量为 W(i)，每件物品价值为 P(i)，在保证不超过最大重量 V 的情况下，放入的物品价值最大？
因为我现在学的贪心算法，也看了看网上说的，贪心算法可以解决这个问题，就使用贪心算法：
依次取 价值除以重量 P(i)/W(i) 最大的放进去就行，但实际上这确实不行的。不知道这种情况算一般算法不，还是我说的这个贪心策略不对。

[DaCong]

@zhangwugui #7 多个是指没有上限吗？如果是的话，就是完全背包问题，我给你的链接里有讲到
我给你的 PDF 就是 6# 说的背包九讲

[zjsxwc]

mark 下， 动态规划主要就是状态转移方程。

我记得背包问题在那个讲解图里面：
01 背包是 斜、 竖 方向的 转移
完全背包是 横、 竖 方向的 转移

[xupefei]

可以放无限次的叫 unbounded knapsack，放一次的叫 0/1 knapsack，可拆分的叫 fractional knapsack。
没有“一般背包”这种说法。

0/1 背包用贪心算法能保证 50%最优解。
fractional knapsack 的贪心算法可以保证最优解：通过事先按照 value/weight 比值排序后逐个选取。

[xupefei]

@xupefei #10 第一句写错了，每个条目最多放 N* 次，N*是常量。

[zhangwugui]

@DaCong 嗯嗯，感谢。大概明白了，我可能太纠结在贪心算法了。去学习学习动态规划。

[zhangwugui]

@xupefei 嗯，多谢指导，明白了。我所说的那种应该就是 unbounded knapsack。

[nicoley]

@zjsxwc 动态规划我个人感觉它就三部曲，状态的定义，状态如何转移，再就是一些边界条件。。而不是你所说的主要是状态转移。。。。（个人愚见，请大家多多指教

[jedihy]

@zhangwugui 面试极少会考到，不是个人兴趣没必要太深究了。

[zhangwugui]

@jedihy 嗯，最近回过头来看算法的时候，又看到了，再了解下。