這篇文章給大家分享的是c++中的貪心算法怎么實(shí)現(xiàn)，相信大部分人都還沒學(xué)會(huì)這個(gè)技能，為了讓大家學(xué)會(huì)，給大家總結(jié)了以下內(nèi)容，話不多說，一起往下看吧。

成都創(chuàng)新互聯(lián)公司專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)、太和網(wǎng)絡(luò)推廣、微信小程序、太和網(wǎng)絡(luò)營(yíng)銷、太和企業(yè)策劃、太和品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們大的嘉獎(jiǎng)；成都創(chuàng)新互聯(lián)公司為所有大學(xué)生創(chuàng)業(yè)者提供太和建站搭建服務(wù)，24小時(shí)服務(wù)熱線：18982081108，官方網(wǎng)址：www.cdcxhl.com

分治法、動(dòng)態(tài)規(guī)劃在此之前沒有記錄下來，學(xué)到貪心算法的時(shí)候，覺得需要總結(jié)一下學(xué)過的東西，也能更好的理解。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)，要滿足最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題，采用自底向上的策略，計(jì)算出最優(yōu)值，找到整體最優(yōu)解。這個(gè)過程有時(shí)候挺難的，主要在寫出遞歸式，要自底向上填表。貪心策略有點(diǎn)像動(dòng)態(tài)規(guī)劃，但在一些方面是不同的，有時(shí)候貪心算法的思想更容易想到。它要滿足子問題最優(yōu)而得到整體最優(yōu)？?jī)蓚€(gè)條件：最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)。滿足貪心選擇性質(zhì)一定滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，而滿足最優(yōu)子結(jié)構(gòu)性質(zhì)不一定滿足貪心選擇性質(zhì)，比如背包問題可以用貪心算法解決，而0-1背包問題只能用動(dòng)態(tài)規(guī)劃。

典型的貪心問題活動(dòng)安排，有n個(gè)活動(dòng)，給出開始時(shí)間和結(jié)束時(shí)間，要盡可能安排多的活動(dòng)（時(shí)間互相不沖突）。解決這個(gè)問題正確的貪心思想是以每個(gè)活動(dòng)結(jié)束時(shí)間為比較變量，按結(jié)束時(shí)間升序排好活動(dòng)次序，接著就進(jìn)行比較選擇。而會(huì)場(chǎng)安排問題與活動(dòng)又有些不同之處，下面是我的解題過程。

7-2 會(huì)場(chǎng)安排問題 (20 分)

假設(shè)要在足夠多的會(huì)場(chǎng)里安排一批活動(dòng)，并希望使用盡可能少的會(huì)場(chǎng)。設(shè)計(jì)一個(gè)有效的 貪心算法進(jìn)行安排。（這個(gè)問題實(shí)際上是著名的圖著色問題。若將每一個(gè)活動(dòng)作為圖的一個(gè) 頂點(diǎn)，不相容活動(dòng)間用邊相連。使相鄰頂點(diǎn)著有不同顏色的最小著色數(shù)，相應(yīng)于要找的最小 會(huì)場(chǎng)數(shù)。）

輸入格式:

第一行有 1 個(gè)正整數(shù)k，表示有 k個(gè)待安排的活動(dòng)。 接下來的 k行中，每行有 2個(gè)正整數(shù)，分別表示 k個(gè)待安排的活動(dòng)開始時(shí)間和結(jié)束時(shí)間。時(shí)間 以 0 點(diǎn)開始的分鐘計(jì)。

輸出格式:

輸出最少會(huì)場(chǎng)數(shù)。

輸入樣例:

5
1 23
12 28
25 35
27 80
36 50

輸出樣例:

3

#include
#include
using namespace std;
struct node {
    int begin;
    int end;
    int flag;//標(biāo)記該活動(dòng)是否被安排，0表示未安排，1表示已安排 
}t[10001];
int cmp(const node &a,const node &b)//比較規(guī)則：以結(jié)束時(shí)間升序排列 
{ 
    return a.end>n;
    for(i=0;i>t[i].begin>>t[i].end;
        t[i].flag=0;
    }
    sort(t,t+n,cmp);
        
    int sum=0;//總共需要的會(huì)場(chǎng)數(shù)量 
    for(i=0;i
貪心策略為：把盡可能多的時(shí)間互不沖突的活動(dòng)安排到一個(gè)會(huì)場(chǎng)，若活動(dòng)時(shí)間交叉，則在安排到另一個(gè)會(huì)場(chǎng)。
將所有活動(dòng)按結(jié)束時(shí)間升序排列，利用sort函數(shù)，自定義cmp方法。循環(huán)體中，每次可以找到還沒有安排的活動(dòng)，并以這個(gè)活動(dòng)搜索能同時(shí)容納到一個(gè)會(huì)場(chǎng)的其他活動(dòng)（這一步嵌套在內(nèi)層循環(huán)中），經(jīng)過兩層循環(huán)，把所有活動(dòng)全部安排好，這時(shí)也已經(jīng)計(jì)算出需要的會(huì)場(chǎng)數(shù)量sum。
類似的問題是區(qū)間選點(diǎn)
7-10 選點(diǎn)問題 (15 分)
數(shù)軸上有n個(gè)閉區(qū)間[ai, bi]。取盡量少的點(diǎn)，使得每個(gè)區(qū)間內(nèi)都至少有一個(gè)點(diǎn)（不同區(qū)間內(nèi)含的點(diǎn)可以是同一個(gè)）。
輸入格式:
第一行一個(gè)數(shù)字n，表示有n個(gè)閉區(qū)間。 下面n行，每行包含2個(gè)數(shù)字，表示閉區(qū)間[ai, bi]
輸出格式:
一個(gè)整數(shù)，表示至少需要幾個(gè)點(diǎn)
輸入樣例:
在這里給出一組輸入。例如：
3
1 3
2 4
5 6
輸出樣例:
在這里給出相應(yīng)的輸出。例如：2
開始想找出幾個(gè)區(qū)間共同段，并且記錄每個(gè)共同段中包含哪些區(qū)間，這樣算出最少選點(diǎn)。后來發(fā)現(xiàn)覺得這個(gè)想法其實(shí)可以簡(jiǎn)化一下，策略為：以右端為擋板，看看前面是否包含其他區(qū)間，如果是，則不記數(shù)，反之，說明沒有共同段，需要計(jì)數(shù)并且移動(dòng)擋板位置繼續(xù)尋找。貪心策略是選擇區(qū)間右端點(diǎn)，保證能夠包含更大交叉段，選的點(diǎn)最少。
#include
using namespace std;
struct dot{
    int l,r;
    bool v[10001];
}dots[10001];
int cmp(const dot &a,const dot &b)//比較規(guī)則，按區(qū)間右端點(diǎn)升序排列 
{
    return a.r>n;
    for(i=0;i>dots[i].l>>dots[i].r;
    sort(dots,dots+n,cmp);//預(yù)處理，將區(qū)間按規(guī)則排好序，方便后續(xù)比較 
    select=dots[0].r;
    //貪心策略是選擇區(qū)間右端點(diǎn)，保證能夠包含更大交叉段，選的點(diǎn)最少 
    for(i=1;iselect)//如果沒有交叉，選點(diǎn)+1,并以此區(qū)間右端為新一輪比較的點(diǎn) 
        {
            count++;
            select=dots[i].r;
        }
    }
    cout<
上述就是小編為大家分享的c++中的貪心算法的實(shí)現(xiàn)方法了，如果您也有類似的疑惑，不妨參照上述方法進(jìn)行嘗試。如果想了解更多相關(guān)內(nèi)容，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊。
            

            文章題目：c++中的貪心算法怎么實(shí)現(xiàn)-創(chuàng)新互聯(lián)            

            本文路徑：http://weahome.cn/article/dejcop.html