貪心/貪婪算法

貪心算法簡介

簡單貪心

貪心法是求解一類最優化問題的方法，它總是考慮在目前狀态下局部最優（較優）的政策，來使全局的結果達到最優（較優），顯然如果采用較優而非最優的政策，得到的全局結果也不一定是最優的。而要獲得最優結果，必須保證中間的每步政策都是最優的，是以嚴謹使用貪心政策來求解最優化問題需要對政策進行證明。一般來說，證明比較繁瑣情況下，如果在想到某個似乎可行的政策，并且自己也無法舉出反例，可以直接大膽使用。

執行個體一月餅

給定所有種類月餅的庫存量，總售價以及市場的最大需求量，試計算可以獲得的最大收益。

輸入格式：正整數N表示月餅種類數（N<=1000）,正整數D表示最大需求量（D<=500萬噸）;随後一行給出N個正整數表示每種月餅的庫存，最後一行給出N個正整數表示每種月餅的總售價。

輸入：在一行中輸出最大收益，以億元為機關并精确到小數點後2位。

容易看出，答案是72+45/2=94.5。原則就是總是采用單價最高的月餅出售。

是以，思路如下：

（1）将所有月餅按照單價從高到低排序。

（2）從單價高的月餅開始枚舉。如果該月餅的庫存不足以填補需求，将該種月餅全部售出。需求量減少該種月餅的庫存大小，收益增加該月餅的總售價。如果月餅庫存足夠填補需求，則隻提供需求量大小的月餅。需求量減為0，收益增加。

#include <cstdio>
#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;
}

貪心/貪婪算法

執行個體二：組個最小數

給定數字0-9若幹個，可以任意順序排列這些數字，但必須全部使用。目标是使得最後得到的數盡可能小（0不可以為首位）。例如給定2個0，2個1，3個5，1個8，得到的最小數就是10015558。

輸入格式：在一行中給出10個非負整數，順序表示擁有數字0，1，......8，9的個數。十個數字的總個數不超過50，而且至少擁有1個非0數字。

輸入
2 2 0 0 0 3 0 0 1 0
輸出
10015558

政策：先從1-9中選擇個數不為0的最小數輸出，然後從0-9輸出數字，每個數字輸出次數就是其剩餘次數。

#include <cstdio>

int main()
{
    int count_num[10];
    for(int i=0;i<10;i++)
    {
        scanf("%d",&count_num[i]);
    }

    for(int i=1;i<10;i++)
    {
        if(count_num[i]>0)
        {
            printf("%d",i);
            count_num[i]--;
            break;
        }
    }

    for(int i=0;i<10;i++)
    {
        while(count_num[i]>0)
        {
            printf("%d",i);
            count_num[i]--;
        }
    }
    return 0;
}

區間貪心

區間不相交問題：給出N個開區間（x,y）,從中選擇盡可能多的開區間，使得這些開區間22沒有交集。例如對于開區間

（1,3）(2,4) (3,5) (6,7)

最多可以選擇3個開區間

(1,3) (3,5) (6,7)

互相沒有交集。

首先考慮最簡單的情況，如果開區間A1被開區間A2包含，那麼顯然選擇開區間A1是最好的選擇。

接着把所有開區間按照左端點x從大到小排序，如果去除掉區間包含的情況，必有y1>y2>y3>.....>yn成立。那麼如何選擇區間。如圖所示：A1的右邊有一段是一定不會和其他區間重疊的，如果把他去掉，那麼A1就會被包含，這時應該選擇A1.是以對于這種情況應該總是先選擇

左端點最大的區間。

貪心/貪婪算法

#include <cstdio>
#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;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&I[i].x,&I[i].y);
    }
    sort(I,I+n,cmp);
    int ans=1;
    int 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】，求最少需要确定多少點，才可以使得每個區間都至少有一個點。

類似，把區間按照左端點由大到小排序，如果A1被A2包含，則在A1區間内的點一定也在A2區間。我們隻需要總是選擇最左邊端點即可，盡可能覆寫多的區間。

隻需修改代碼如下即可

I[i].y<=lastX;
I[i].y<lastX;

顯然貪心算法用來解決一類最優化問題，并希望由局部最優政策來推得全局最優政策。貪心算法适用的問題一定滿足最優子結構的問題。

變種

求區間的交集：合并有交集的區間[1,4，[2,6，[6,7 合并結束是[1,7

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
const int maxn=105;

struct Interval
{
    int x,y;
}I[maxn];

bool cmp(Interval I1,Interval I2)
{
    if(I1.x!=I2.x)
        return I1.x<I2.x;
    else
        return I1.y>I2.y;
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>I[i].x;
        cin>>I[i].y;
    }
    sort(I,I+n,cmp);
    vector<Interval> res;

    Interval temp=I[0];
    for(int i=1;i<n;i++)
    {
        if(I[i].y<=temp.y)
            continue;
        else if(I[i].x<=temp.y)
            temp.y=I[i].y;
        else if(I[i].x>temp.y)
        {
            res.push_back(temp);
            temp=I[i];
        }
    }
    res.push_back(temp);
    for(int i=0;i<res.size();i++)
    {
        cout<<res[i].x<<" "<<res[i].y<<endl;
    }
}

執行個體三

貪心/貪婪算法

這是一道典型的貪心算法，為了避免多吃的危險，我們在最初先不要消耗一份一盒包裝的雪糕，而應該總是選擇消耗一份一盒包裝的蛋糕最小的方法。即按照下面的方法進行

消耗2盒3包裝的蛋糕/3盒2包裝的蛋糕     這時消耗1盒包裝的最少，為0

消耗1盒3包裝的蛋糕，再消耗1盒2包裝的蛋糕    此時消耗1盒包裝數為1

消耗2盒2包裝的蛋糕           此時消耗1盒蛋糕數目為2

消耗1盒3包裝的蛋糕           此時消耗1盒蛋糕數目為3

消耗1盒2包裝的蛋糕            此時消耗1盒蛋糕數目為4
                        
                            此時消耗1盒蛋糕數目為6

#include <cstdio>
#include <iostream>

using namespace std;
int t;

bool pan_duan(int n,int a,int b,int c)
{
    int day=0;
    if(c>=2)
    {
        day+=c/2;
        c%=2;
    }
    if(b>=3)
    {
        day+=b/3;
        b%=3;
    }
    while(c>=1&&b>=1&&a>=1)
    {
        day+=1;
        c-=1;
        b-=1;
        a-=1;
    }
    while(b>=2&&a>=2)
    {
        day+=1;
        b-=2;
        a-=2;
    }
    while(c>=1&&a>=3)
    {
        day+=1;
        c-=1;
        a-=3;
    }
    while(b>=1&&a>=4)
    {
        day+=1;
        b-=1;
        a-=4;
    }
    day+=a/6;
    if(day>=n)
        return true;
    else
        return false;
}

int main()
{
    scanf("%d",&t);
    int n,a,b,c;
    for(int i=0;i<t;i++)
    {
        scanf("%d%d%d%d",&n,&a,&b,&c);
        if(pan_duan(n,a,b,c))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

貪心/貪婪算法

部落格分享

小船過河問題

隻有一艘船，能乘2人，船的運作速度為2人中較慢一人的速度，過去後還需一個人把船劃回來，問把n個人運到對岸，最少需要多久。

（1）當隻有2個人時，過河時間是t2（t1<t2）

（2）當隻有3個人時，過河時間是t1+t2+t3，即最快的把另一個送過河，再傳回來送另一個。

（3）當人數多時，>=4時，可以考慮每次都把最慢和次慢的送走。這個時候又有2種方式。

1）最快的把次快的送過去，自己回來，然後最慢的和次慢的過河，已經在對岸的次快把船劃回來。時間為a[0]+2a[1]+a[n-1]

2）最快的把最慢送過去，自己回來，然後把次慢（這個時候已經是最慢了）送過河，自己再回來。時間為2a[0]+a[n-2]+a[n-1]

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }

    sort(a,a+n);

    int sum=0;
    while(n>3)
    {
        sum+=min(a[0]+2*a[1]+a[n-1],2*a[0]+a[n-2]+a[n-1]);
        n-=2;
    }
    if(n==3)
        sum+=a[0]+a[1]+a[2];
    else if(n==2)
        sum+=a[1];
    else
        sum+=a[0];
    cout<<sum<<endl;
    return 0;
}

動态規劃解法：

程式員算法基礎——貪心算法 - 簡書

貪心/貪婪算法

貪心算法簡介

簡單貪心

執行個體一月餅

執行個體二：組個最小數

區間貪心

變種

執行個體三

小船過河問題

繼續閱讀

【趨高機器視覺】機器視覺技術原了解析及解決方案

[轉]ISUP信令的IAM消息詳細内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

C語言：初學者必定看懂的注釋！！！猴子吃桃問題。猴子第一天摘下若幹個桃子，每天都吃了前一天剩下的一半零一個，到第10天早上想再吃的時候，就剩下一個桃子. 求第一天共摘多少個桃子。

[轉]九大排序算法——C語言實作及詳解

筆試面試題目：滑動視窗(二)

while 循環、do- while 循環和 for 循環之間的那點事C語言自學之三種循環比較

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

結構體：typedef與struct的差別

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希

貪心/貪婪算法

貪心算法簡介

簡單貪心

執行個體一 月餅

執行個體二：組個最小數

區間貪心

變種

執行個體三

小船過河問題

繼續閱讀

執行個體一月餅