0-1背包问题具有贪心选择性质吗?证明之

2024-12-03 02:02:41
推荐回答(3个)
回答1:

首先按物品的重量从小到大排序。贪心选择性质说的就是每次都是都是选取当前的最优值。假设背包问题每次都是从重量最小的物品开始选择的,那他一定满足贪心选择性质,假设背包问题不是从重量最小的物品开始选择的,那么说明重量最小的物品没有装入,现在我们用这个重量最小的物品代替当前选择装入的物品,依然可以得到一个最优解(装入的物品的个数相同)。所以背包问题具有贪心选择性质

回答2:

0-1背包问题不能用贪心法解决,但是部分背包问题可以用贪心法解决。首先0-1背包是要么不拿,要拿就得把这类物品全部拿完部分背包问题的贪心算法正确性证明可以参考这个看看

回答3:

无法证明你的问题