4 四 贪心算法 习题参考答案

《4 四 贪心算法 习题参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章作业部分参考答案1．设有个顾客同时等待一项服务。顾客需要的服务时间为。应该如何安排个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。试给出你的做法的理由（证明）。策略：对进行排序，然后按照递增顺序依次服务即可。解析：设得到服务的顾客的顺序为，则总等待时间为则在总等待时间T中的权重最大，的权重最小。故让所需时间少的顾客先得到服务可以减少总等待时间。证明：设，下证明当按照不减顺序依次服务时，为最优策略。记按照次序服务时，等待时间为，下证明任意互换两者的次序，都不减。即假设互换两位顾客的次序，互换后等待总时间为，则有由于则有同理可证其它次序

2、，都可以由经过有限次两两调换顺序后得到，而每次交换，总时间不减，从而为最优策略。2．字符出现的频率分布恰好是前8个Fibonacci数，它们的Huffman编码是什么？将结果推广到个字符的频率分布恰好是前个Fibonacci数的情形。Fibonacci数的定义为：解：前8个数为a，b，c，d，e，f，g，h1，1，2，3，5，8，13，21Huffman哈夫曼编码树为：54h:21332012742g:13f:8e:5d:3C:2b:1a：101000000111111所以a的编码为：1111111b的编码为：1111110c的编码为：111110d的编码为：11110e的编

3、码为：1110f的编码为：110g的编码为：10h的编码为：0推广到n个字符：第1个字符：n-1个1，第2个字符：n-2个1，1个0，第3个字符：n-3个1，1个0，……第n-1个字符：1个1，1个0，10第n个字符：1个0，01．设是准备存放到长为L的磁带上的n个程序，程序需要的带长为。设，要求选取一个能放在带上的程序的最大子集合（即其中含有最多个数的程序）。构造的一种贪心策略是按的非降次序将程序计入集合。1)证明这一策略总能找到最大子集，使得。2)设是使用上述贪心算法得到的子集合，磁带的利用率可以小到何种程度？3)试说明1)中提到的设计策略不一定得到使取最大值的子集合。1

4、）证明：不妨设，若该贪心策略构造的子集合为，则满足、。要证明能找到最大子集，只需说明s为可包含的最多程序段数即可。即证不存在多于s个的程序集合，使得。反证法，假设存在多于s个的程序集，满足。因为非降序排列，则。因为且为整数，则其前s+1项满足。这与贪心策略构造的子集和中s满足的矛盾。故假设不成立，得证。2）磁带的利用率为;（甚至最小可为0，此时任意或者）3)按照1）的策略可以使磁带上的程序数量最多，但程序的总长度不一定是最大的，假设为Q的最大子集，但是若用代替，仍满足，则为总长度更优子集。