Question

0-1背包问题到底能用贪心法解决吗？

Answer 1

0-1背包问题不能用贪心法解决，但是部分背包问题可以用贪心法解决。首先0-1背包是要么不拿，要拿就得把这类物品全部拿完。网页链接可以参考这个看看

Answer 2

首先按物品的重量从小到大排序。贪心选择性质说的就是每次都是都是选取当前的最优值。假设背包问题每次都是从重量最小的物品开始选择的,那他一定满足贪心选择性质,假设背包问题不是从重量最小的物品开始选择的,...