第4章贪心算法
实验4.1 贪心算法的实现与时间复杂度测试
1. 实验目的
编程实现经典的贪心算法，理解贪心算法设计的基本思想、程序实现的相关技巧，加深对贪心算法设计与分析思想的理解。

通过程序的执行时间测试结果，与理论上的时间复杂度结论进行对比、分析和验证。

2. 原理解析
贪心算法的基本思想
贪心算法求解优化问题的基本思想是：采用逐步构造最优解的方法。

在每个阶段，都做出一个当前最优的决策（在一定的标准下）。

决策一旦做出，就不可再更改（做出贪心决策的依据称为贪心准则）。

贪心算法的一般步骤如下：
(1) 根据拟解决问题选取一种贪心准则；
(2) 按贪心准则标准对n个候选输入排序（以这一方法为代表，仍可基于堆来存储候选）；
(3) 依次选择输入量加入部分解中：如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。

贪心算法的基本设计范式如下：
Greedy(A,n)
A: include n inputs
Solution=Ф
for i=1 to n do
x=Select(A)
if Feasible(solution,x) then
solution=Union(solution,x)
end if
end for
return solution
测试算法
背包问题是使用贪心算法求解的代表问题，算法如下：
KnapsackGreedy(p，w，m，x，n)
//v[1..n]和w[1..n]分别含有按vi/wi v(i+1)/v(i+1)排序的n 件物品的价值和重量。

M是背包的容量大小，而x[1..n]是解向量// for i=1 to n do
xi=0 //将解向量初始化为零//
end for
cu=m //cu是背包剩余容量//
for i=1 to n do
if wi>cu then
exit
end if
xi=1
cu=cu-wi
repeat
if i≤n then
xi=cu/wi
end if
算法的时间复杂度取决于对v i/w i排序的时间复杂度，例如，若选择MergeSort 排序算法，则以上算法的时间复杂度为O(n log n)。

3. 实验内容
（1）编程实现以上求解背包问题的贪心算法，并通过手动设置、生成随机数获得实验数据。

记录随着输入规模增加算法的执行时间，分析并以图形方式展现增长率；测试、验证、对比算法的时间复杂度。

（2）利用贪心算法思想，设计实现单源最短路径问题的算法，并编程实现。

4. 实验步骤和要求
实验内容（1）步骤：
(1) 编程实现以上KnapsackGreedy算法，并进行测试，保证程序正确无误。

其中，分别在程序开始和结束处设置记录系统当前时间的变量、用于计算程序执行的时间（以毫秒(ms)作为时间的计数单位）。

(2) 设定一个m值（背包容量），测试随着n增加、程序执行时间增加的趋势。

分别使用实验1中的随机数生成算法生成n个随机数作为n个物品的重量，再生成n个随机数作为n个物品的价值（n=10, 20, 40, 100, 200, 400, 800, 2000）。

记录随着n增加程序的执行时间，并使用MS Excel图表绘制工具生成程序执行时间的对比曲线图。

(3) 与理论上的时间复杂度结论进行对比分析，完成实验报告。

实验内容（2）步骤：
（1）分析该问题的贪心选择性质；
（2）分析该问题的最优子结构性质；
（3）算法的设计与实现；。