这不是一个正确的，但非常有效和简单的方法来解决0-1背包？

据我所知，在0-1背包问题中，只允许0或1个相同变体的对象。把它的价值除以每个重量得到相应的比率，然后把每个比例从最大的开始并放在背包中，直到达到最大允许重量，不是更好吗？它的时间复杂性不会比动态编程解决方案更好，并且明显优于bruteforce？这不是一个正确的，但非常有效和简单的方法来解决0-1背包？

来源

2017-04-18 Ajay_C

它简单高效，但并不总是产生最佳解决方案。如果你自己找不到反例，搜索“贪婪的0-1背包”，谷歌会产生大量的链接。 –

这个贪婪的技巧是众所周知的，但只适用于背包的线性放松。否则，你可以（误导性地）写“直到达到最大重量”，但它可能永远不会达到，早期的选择可以强迫你进入一个角落，在那里你有剩余空间，没有物品适合，尽管你可能已经填满它项目没有被选中。如果你选择价值=权重，那很明显，这会如何导致次优的解决方案 - 这是一个普遍的问题，但这只是显而易见的。 – harold

重量：4,3,2。最大总数：5 –

0-1背包问题的要点在于如果物品放入背包或未包含在背包中，是否会发生最大值。这可以防止包含物品导致背包中的空间不足的问题。一个总是包含一个物体的贪婪方法可能会导致背包里的空间不足。

来源

2017-04-20 07:09:33

谢谢您的回答！虽然我听说有一些贪婪的算法，但我从来没有打扰过查看它。 –

这不是一个正确的，但非常有效和简单的方法来解决0-1背包？

回答

相关问题