信息学试题讲解-贪心策略应用实例分析

问题的提出

贪心策略求解的问题具有的特点：可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。
问题：部分背包问题。给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。

例题分析及算法解答

分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。
算法：

问题初始化；　　　　　　　　　　{读入数据}

按Vi从大到小将商品排序；

I := 1;

repeat

if M = 0 then Break; 　　{如果卡车满载则跳出循环}

M := M - Wi;

if M >= 0 then 将第I种商品全部装入卡车

else

将(M + Wi)重量的物品I装入卡车;

I := I + 1; 　　{选择下一种商品}

until (M <= 0) OR (I >= N)

0,1背包问题

给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。

算法： 按贪心法,有反例.

设N=3，卡车最大载重量是100，三种动物A、B、C的重量分别是40，50，70，其对应的总价值分别是80、100、150。