计算机算法设计与分析(第3版)[王晓东编著][电子教案第4章(17)

计算机算法设计与分析(第3版)[王晓东编著][电子教案

4.2 贪心算法的基本要素用贪心算法解背包问题的基本步骤：首先计算每种物品单位重量的价值Vi/Wi,然后，依贪心 选择策略，将尽可能多的单位重量价值最高的物品装入背包。 若将这种物品全部装入背包后，背包内的物品总重量未超过 C,则选择单位重量价值次高的物品并尽可能多地装入背包。 依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下页：