文档介绍：贪婪算法分析与设计
要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设 计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和 处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的 对象，程序结构、函的需求呢？
设各种饮料的满意度已知，令x为婴儿将要饮用的第i种饮料的量，则需
i
要解决的问题是：找到一组实数x (lWiWn),使》sx最大，并满足= t
i i i i
i-1 i=1
及 0W x W a。
ii
需要指出的是：如果£a〈 t,贝怀可能找到问题的求解方案，因为即使
i
i=1
喝光所有的饮料也不能使婴儿解渴。
对上述问题精确的数学描述明确地指出了程序必须完成的工作，根据这
些数学公式，可以对输入/ 输出作如下形式的描述：
输入：n, t, s , a (其中lWiWn, n为整数，t、s、a为正实数)。
i i i i
输出：实数x (lWiWn)，使丫 s x最大且丫 x =t (0Wx Wa )。如果
i i i i i i
i=1 i=1
》a <t,则输出适当的错误信息。
i
i=1
在这个问题中，限制条件是二t且0Wx Wa , lWiWn。而优化函数
i i i
i=1
是£ s x。任何满足限制条件的一组实数x都是可行解，而使£ s x最大的可行
i i i i i
i=1 i=1
解是最优解。
三、贪婪算法设计
在贪婪算法(greedy method)中采用逐步构造最优解的方法。在每个阶 段,都作出一个看上去最优的决策(在一定的标准下)。决策一旦作出,就 不可再更改。作出贪婪决策的依据称为贪婪准则(greedy cri terion)。
例2 ［装载问题］ 有一艘大船准备用来装载货物。问题简述如下：设有
编号为0,1,…，n-1的n种物品，体积分别为v , v，…，v 。将这n种物
0 1 n -1
品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V,即对于
0WiVn,有0Vv WV。不同的装箱方案所需要的箱子数目可能不同，装箱问
i
题要求使装尽这n种物品的箱子数要少。若考察将n件物品的集合分划成n 个或小于n个物品的所有子集，最优解就可以找到，但所有可能分划的总数 太大。对适当大的n,找出所有可能的划分要划分的时间是无法承受的。为此， 对装箱问题采用非常简单的近似算法，即贪婪法。该算法依次将物品放到它 第一个能放进去的箱子中，该算法虽然不能保证找到最优解，但还是能找到 非常好的解。不失一般性，设n件物品的体积是按从小到大排好序的，即有: v三v三…三v 。如不满足上述要求，只要先对这n件物品按它们的体积从 0 1 n 1
大到小排序，然后按排序结果对物品重新编号即可。装箱算法简单描述如下
{输入箱子的容积；
输入物品种数 n；
按体积从大到小顺序，输入各物品的体积；
预置已用箱子链为空；
预置已用箱子计数器box_count为0；
for(i=0;iVn;i++){
从已用的第一只箱子开始顺序寻找能放入物品i的箱子j；
if(已用箱子都不能再放物品i){ 另用一只箱子，并将物品 i 放入该箱子； box_count++;
}
else
将物品 i 放入箱子 j；