Question

证明题：用解背包问题的贪心算法解0-1背包问题时不一定得到最优解 急求！！

Answer 1

贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最优解上加以考虑，它所作出的选择只是在某种意义上的局部最优解。
背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。
用贪心算法求解背包问题的步骤是，首先计算每种物品单位重量的价值vi/wi；然
后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总量未超过c，则选择单位重量价值次高的物
品并尽可能多地装入背包。依此策略一直进行下去，直到背包装满为止。
在最后一步包装不下时可能会分割物品，而0-1背包问题不能分割物品，故不一定得到最优解。
取一反例即可说明

追问

谢谢您的回答！能否用标准证明格式来证明这个题目呢？

追答

证明的话 去图书馆找算法类书吧，书上都有。写不出来了