算法设计与分析 习题3 学习课件

1.设有n个物品，第i个物品的价值是vi、重量是wi,假设物品可以任意分割，给定一个背包，其能容纳最大重量为C,求该背包能容纳物品的最大价值要求写出伪代码并分析算法正确性和复杂性

2.有6种硬币，面值是1分,2分,5分，1角，5角，1元，给定一个钱数n,求出一个硬币组合，要求面值总和为n且硬币个数最少，假设每种硬币个数无限要求写出伪代码并分析算法正确性和时间复杂性

3.存放于磁带上文件需要顺序访问故假设磁带上依次存储了〃个长度分别是，1],・・・./[〃]的文件，则访问第攵个文件的代价为尸】现给定〃个文件的长度，.…川川，并假设每个文件被访问的概率相等,试设计一个算法输出这〃个文件在磁带上的存储顺序使得平均访问代价最小答案要求包含以下内容

（1）证明问题具有贪心选择性；

（2）证明问题具有优化子结构；

（3）给出算法并分析算法的时间复杂度

4.设有n个正整数，将它们连接成一排，组成一个最大的多位整数例如n=3时,3个整数13,312,343,连成的最大整数为34331213又如n=4时，4个整数7,13,4,246,连成的最大整数为7424613输入是n个正整数，输出是这n个正整数连成的最大多位整数，要求用贪心法求解该问题答案要求包含以下内容

（1）证明问题具有贪心选择性；

（2）证明问题具有优化子结构；

（3）写出算法伪代码并分析算法的时间复杂度

5.设xl,x2,….，xn是实数轴上的n个点，若用单位长度的闭区间覆盖这些点，至少需要多少单位长度闭区间？

6.考虑下述最小生成树算法，初始时，G中的每个顶点被视为一个单结点的树，不选择任何边，在每一步，为每棵树选择一条最小权的边e,是的e只有一个顶点在T中，如果必要的话，出去所选边的备份，当只得到一棵树或者所有边都被选中了，那么终止算法证明算法的正确性并且求出算法的最大步数7G=（V,E）是一个具有n个顶点m条边的连通图，且可以假设边的代价为正.且各不相同，设，定义T的瓶颈边是T中代价最大的边，G的一个生成树T是一棵最小瓶颈生成树，如果不存在G的生成树T是的它具有代价更小的瓶颈边问

（1）G的每棵最小瓶颈树一定是G的一棵生成树吗？证明或者给出反例；

（2）G的每棵生成树都是G的最小瓶颈树吗？证明或者给出反例

8.给定n个自然数dl,d2,…，dn,设计算法，在多项式时间确定是否存在一个无向图G,使它的结点度数准确地就是dl,d2,…，dn,要求G中在任意两个结点之间至多有一条边，且不存在一个结点到自身的边

9.考虑一种特殊的0-1背包问题，有n个物品，每个物品价值和重量都相等,背包能容纳的最大重量是C,回答下列问题若物品的重量价值分别是1,2,…,2,证明该0-1背包问题可以用贪心法求解并写出该贪心法请写出一个物品重量价值序列，使得上述贪心法无法得到最优解

10.考虑下述“逆贪心”算法，输入是连通有权无向图G,用邻接表描述；REVERSEC REEDY\IST7sort thoedges Eof Gby weightfor t1to|E|e zthheaviest edgein Eif G\e isconnected removee fromG

1.该算法的最坏运行时间是多少？在什么情况下发生？2,证明这个算法可以找到G的最小生成树。