顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。
虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
局部最优->整体最优

题目1

Description
给定一个非负整数数组，假定你的初始位置为数组第一个位置。数组中的每个元素代表你在那个位置能够跳跃的最大长度。你的目标是到达最后一个下标位置，并且使用最少的跳跃次数。
Input
输入一组非负整数数组，数组长度不超过500。
Output
最少经过几次跳跃，可以到达最后一个位置。
Sample Input
2 3 1 1 4
Sample Output
2
算法思想
每次都遍历当前位置所能到达的位置，跳到数字最大即可
代码
#include
using namespace std;
int main()
{
int arr[511];
int n = 0;
int k;
// 输入
while(cin >> k)
{
char x = cin.get();
arr[n++] = k;
if(x == ‘\n’)
break;
}
int i=0;
int count = 0;
if(n==1)
{
cout << 0 << endl;
return 0;
}
while(true)
{
//如果当前位置可以直接跳到终点
if(i+arr[i]>=n-1)
{
count++;
break;
}
// 找到当前位置所能跳跃范围内最大的数
int maxNum = -1;
int maxIndex;
for(int j=i+1; j<=i+arr[i]; j++)
if(arr[j]>maxNum)
{
maxNum = arr[j];
maxIndex = j;
}
i = maxIndex; // 跳跃到最合适的位置
count++;
}
cout << count << endl;
return 0;
}

算法2

问题描述
有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。
输入文件
第一行为n(≤1000)；
第二行分别表示第1个人到第n 个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。
输出文件
一个数，平均等待时间(输出结果精确到小数点后两位)。
输入样例
10
56 12 1 99 1000 234 33 55 99 812
输出样例
291.90
要使每个人平均等待时间最小,当然是接水时间小的排在前面了，因此解法如下
#include
using namespace std;
struct Edge {
int num,id; } a[1000];
int cmp(Edge x,Edge y) {
if(x.num==y.num)
return x.id else return x.num }
int main() {
int n,i,sum=0;
cin>>n;
for(i=0;i cin>>a[i].num;
a[i].id=i+1; }
sort(a,a+n,cmp);
for(i=0;i sum+=a[i].num(n-i-1); }
printf(“%.2f”,sum1.0/n);
return 0;
}

算法3

Description
给出n个区间的起点和终点，求最少使用其中多少个区间可以将所有区间所在的区域完全覆盖。（测试的数据确保这1点）。

Input
第1行一个整数n，表示n个区间；
第2行开始n行，每行2个整数，表示一个区间范围。

Output
按区间先后顺序，输出选中的区间。

Sample Input
7
1 5
1 6
3 6
1 7
6 9
9 10
7 9

Sample Output
1 7
6 9
9 10

算法思想
将区间按照左端点从小到大排序，左端点相同按右端点从小到大排序
每次都找到左端点在已覆盖区域内，右端点尽可能长的区间
#include
#include
using namespace std;
class Section{
public:
int num1;
int num2;
};
// 根据区间的左端点进行升序排序
// 左端点一致的根据右端点升序排序
bool cmp(Section s1, Section s2){
if(s1.num1 return true;
else if(s1.num1==s2.num1 && s1.num2 return true;
else
return false;
}
int main()
{
Section a[100];
Section r[100];
int n, cnt = 0; // 区间的个数 覆盖所需区间的个数
cin >>n;
for(int i=0; i cin >> a[i].num1 >> a[i].num2;
}
sort(a, a+n, cmp);
int right = a[0].num1-1, end = a[n-1].num2; // 覆盖区域的右端点 区域的终点
// 找到一个区间左端点在已覆盖区域内，右端点尽可能长
for(int i=0; i int max_right = a[i].num2, max_index = i;
while(a[i].num1<=right+1 && i if(a[i].num2>max_right){
max_right = a[i].num2;
max_index = i;
}
i++;
}
right = max_right;
r[cnt++] = a[max_index];
i = max_index;
//cout << “i==” << i << endl;
if(right == end)
break;
}
for(int i=0; i cout << r[i].num1 << “ “ << r[i].num2 << endl;
}
return 0;
}

背包问题（物品可分）

题目

有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

思路

具有最优子结构性质和贪心选择性质。只要是所有物品的总重量大于背包容纳量，那么背包一定能装满。注意背包问题与0-1背包问题的区别。
这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。

求解步骤

用贪心算法解背包问题的基本步骤：首先计算每种物品单位重量的价值v[i]/w[i]，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。

代码实现

include
#include
#define MAX_NUM 1000
using namespace std;
struct Goods //info of goods定义物品信息结构体
{
int weight; // the weight of goods重量
int value ; // the value of goods价值
double ValPerWei; // value per weight权重
double load; //物品装入背包的部分的系数
};
int cmp( Goods const &a, Goods const &b) //定义sort函数的比较函数
{
if(a.ValPerWei else return 1;
}
void Greedy(Goods g[],int good_num, int content) //贪心算法
{
for(int i=0; i {
if(content>g[i].weight) //如果背包足够装下整个物品
{
content-=g[i].weight;
g[i].load=1;
}
else if(content>0){ //如果背包不足以装下整个物品
g[i].load=(double)content/g[i].weight; //计算物品装入背包的部分
content=0; //背包容量置0
return; //程序结束，返回
}
}
}
int main()
{
int goods_num;
int bagvol;
double total_value=0;
double total_weight=0;
cout<<”Please input the volum of bag:”< cin>>bagvol;
cout<<”Please input the number of goods:”< cin>>goods_num;
Goods G[goods_num+1];
cout<<”Please inuput the weight and value of goods:”< for(int i=0; i {
cin>>G[i].weight>>G[i].value; //输入重量价值
G[i].ValPerWei=(double)G[i].value/G[i].weight; //计算权重
G[i].load=0; //load置0
}

sort (G,G+goods_num,cmp); //sort by ValPerWei
Greedy(G,goods_num,bagvol);
cout<<”Info of loaded goods:”< for(int i=0;i {
if(G[i].load==0.0)break; //如果检测到物品未被装入背包，则推出循环

total_value+=(G[i].valueG[i].load); //装入背包的物品总价值
total_weight+=(G[i].weightG[i].load); //装入背包的物品总重量
cout<<”weight: “< }
cout<<”the volum of bag is: “< cout<<”the total weight is: “< cout<<”the total value is: “<}