贪 心

简单贪心

贪心法是求解一类最优化问题的方法,它总是考虑在当前状态下局部最优(或较优)的策略,来使全局的结果达到最优(或较优)。显然,如果采取较优而非最优的策略(最优策略可能不存在或是不易想到),得到的全局结果也无法是最优的。而要获得最优结果,则要求中间的每步策略都是最优的,因此严谨使用贪心法来求解最优化问题需要对采取的策略进行证明。证明的一般思路是使用反证法及数学归纳法,即假设策略不能导致最优解,然后通过一系列系列推导来得到矛盾,以此证明策略是最优的,最后用数学归纳法保证全局最优。不过对平常使用来说,也许没有时间或不太容易对想到的策略进行严谨的证明(贪心的证明往往比贪心本身更难),因此一般来说, 如果在想到某个似乎可行的策略,并且自己无法举出反例,那么就勇敢地实现它。
PAT1024B

#include<iostream>
#include<algorithm>
using namespace std;
struct mooncake{
    double store;
    double sell;
    double price;
}cake[1010];
bool cmp(mooncake a,mooncake b){
    return a.price>b.price;
} 
int main(){
    int n;
    double D;
    scanf("%d%lf",&n,&D);
    for(int i=0;i<n;i++){
        scanf("%lf",&cake[i].store);
    }
    for(int i=0;i<n;i++){
        scanf("%lf",&cake[i].sell);
        cake[i].price=cake[i].sell/cake[i].store;
    }
    sort(cake,cake+n,cmp);
    double ans=0;
    for(int i=0;i<n;i++){
        if(cake[i].store<=D){
            D-=cake[i].store;
            ans+=cake[i].sell;
        }else{
            ans+=cake[i].price*D;
            break;
        }
    }
    printf("%.2f\n",ans);
    return 0;
}

区间贪心
区间不相交问题:给出N个开区间(x,y),从中选择尽可能多的开区间,使得这些开区间两两没有交集。
如果开区间i1被开区间i2包含,那么显然选择i1是最好的选择。所以总是选择左端最大的区间。

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=110;
struct Inteval{
    int x,y;
}I[maxn];
bool cmp(Inteval a,Inteval b){
    if(a.x!=b.x) return a.x>b.x;
    else return a.y<b.y;
}
int main(){
    int n;
    while(scanf("%d",&n),n!=0){
        for(int i=0;i<n;i++){
            scanf("%d%d",&I[i].x,&I[i].y);
        }
        sort(I,I+n,cmp);
        int ans=1,lastX=I[0].x;
        for(int i=1;i<n;i++){
            if(I[i].y<=lastX){
                lastX=I[i].x;
                ans++; 
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

区间选点问题:给出N个闭区间[x,y],求最少需要确定多少个点,才能使没个闭区间中都至少存在一个点。例如对闭区间[1,4]、[2,6]、[5,7]来说,需要两个点才能保证每个闭区间都至少存在一个点。事实上,这个问题和区间不相交问题策略是一样的。

贪心是用来解决一类最优化问题,并希望由局部最优策略来推得全局最优结果的算法思想。贪心算法适用的问题一定满足最优子结构性质,即一个问题的最优解可以由它的子问题的最优解有效地构造出来。

标签: none

评论已关闭