贪心算法小结

贪心算法
一.定义.在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出每个问题的最优解，这种求解方法就是贪心算法。
二.性质：贪心算法不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身得特性决定了该题运用贪心算法可以得到最优解。
三.贪心算法解决的题型

1.背包问题

有两类背包问题（根据物品是否可以分割），如果物品不可以分割，称为0—1背包问题（动态规划）；如果物品可以分割，则称为背包问题（贪心算法）

例如：给定一个载重量为M的背包，考虑n个物品，其中第i个物品的重量 ，价值wi （1≤i≤n），要求把物品装满背包，且使背包内的物品价值最大。(背包问题运用贪心算法）

struct bag{
	int w;			//物品的重量
	int v;			//物品的价值
	double c;		//性价比
}a[1001];			//存放物品的数组
排序因子（按性价比降序）：
bool cmp(bag a, bag b){
	return a.c >= b.c;
}
sort(a, a+n, cmp);
//形参n是物品的数量，c是背包的容量M，数组a是按物品的性价比降序排序
double knapsack(int n, bag a[], double c)
{
　　double cleft = c;　　　　　　　　//背包的剩余容量
　　int i = 0;
　　double b = 0;　　　　　　　　　　//获得的价值
　　//当背包还能完全装入物品i
　　while(i<n && a[i].w<cleft)
　　{
　　　　cleft -= a[i].w;
　　　　b += a[i].v;
　　　　i++;
　　}
　　//装满背包的剩余空间
　　if (i<n) b += 1.0*a[i].v*cleft/a[i].w;
　　return b;
}

例如：金银岛问题
某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为w的物品。岛上金属有s个种类,
每种金属重量不同，分别为n1,n2,…,ns，同时每个种类的金属总的价值也不同，分别为v1,v2, …,
vs。KID想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。

【输入】

第1行是测试数据的组数k，后面跟着k组输入。

每组测试数据占3行，第1行是一个正整数w(1<=w<=10000)，表示口袋承重上限。第2行是一个正整数s(1<=s<=100)，表示金属种类。第3行有2s个正整数，分别为n1,v1,n2,v2,…,ns,vs分别为第一种，第二种，…，第s种金属的总重量和总价值(1<=ni
<=10000,1<=vi<=10000)。

【输出】

k行，每行输出对应一个输入。输出应精确到小数点后2位。

【输入样例】

2
50
4
10 100 50 30 7 34 87 100
10000
5
1 43 43 323 35 45 43 54 87 43

【输出样例】

171.93
508.00

#include <iostream>  

#include <iomanip> 

#include <algorithm>  

using namespace std;  

struct metal  

{  

    double w;  

    double v;  

    double price;  

}a[201];  

double comp(metal a1,metal a2)  

{  

    return a1.price>a2.price;  

}  

int main()  

{  

    int k;  

    cin>>k;  

    while(k--)  

    {  

        double result=0;  

        double w;  

        int s;  

        cin>>w>>s;  

        double tempW,tempV;  

        for(int i=0;i<s;i++)  

        {  

            cin>>tempW>>tempV;  

            a[i].w = tempW;  

            a[i].v = tempV;  

            a[i].price = tempV/tempW;  

        }  

        sort(a,a+s,comp);  

        for(int i=0;i<s;i++)  

        {  

            if(w>=a[i].w)  

            {  

                result+=a[i].v;  

                w-=a[i].w;  

            }else   //考虑w装下所有金属并有空余  

            {  

                result+=w*a[i].price;  

                break;  

            }  

        }  

        cout<<fixed<<setprecision(2)<<result<<endl;  

    }  

}  

2.多处最优服务次序问题
例如：接水问题
问题描述
　　学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的 供水量相等，均为1。 现在有n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1 到n 编号，i 号同学的接水量为wi。接水开始时，1 到m 号同学各占一个水龙头，并同时打 开水龙头接水。当其中某名同学j 完成其接水量要求wj 后，下一名排队等候接水的同学k 马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即 j 同学第x 秒结束时完成接水，则k 同学第x+1 秒立刻开始接水。若当前接水人数n’不足m， 则只有n’个龙头供水，其它m−n’个龙头关闭。 现在给出n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。
输入格式
　　第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数。 第2 行n 个整数w1、w2、……、wn，每两个整数之间用一个空格隔开，wi 表示i 号同 学的接水量。
输出格式
　　输出只有一行，1 个整数，表示接水所需的总时间。
样例输入
5 3
4 4 1 2 1
样例输出
4
样例输入
8 4
23 71 87 32 70 93 80 76
样例输出
163

#include<iostream>
#include<cstdio>
#include<cstring> using namespace std;
int n,m,j,w=0;//计有几个人已经接完了水 int a[10005];//开数组 int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d ",&a[i]);
    for(int i=1;m+w<n;i++)//接完水的人加正在接水的人小于等于总人数,枚举每一分钟     {
        j=0;
        while(1)
        {//查找正在接水的人中有没有接完的 if(a[j]==i){a[j]+=a[m+w];w++;}//有接完的便让后一个加上来 if(j==m-1)break;//这一排没有就退出 j++;
        }
    }
    sort(a,a+n);
    printf("%d",a[n-1]);
    return 0;
}