c++中的貪心算法怎么實現(xiàn)-創(chuàng)新互聯(lián)

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

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

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

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

7-2 會場安排問題 (20 分)

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

輸入格式:

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

輸出格式:

輸出最少會場數(shù)。

輸入樣例:

輸出樣例:

#include<iostream>
#include<algorithm>
using namespace std;
struct node {
    int begin;
    int end;
    int flag;//標記該活動是否被安排，0表示未安排，1表示已安排 
}t[10001];
int cmp(const node &a,const node &b)//比較規(guī)則：以結(jié)束時間升序排列 
{ 
    return a.end<b.end;
 } 
int main()
{
    int i,j,n;
    node temp;
    cin>>n;
    for(i=0;i<n;i++) 
    {
        cin>>t[i].begin>>t[i].end;
        t[i].flag=0;
    }
    sort(t,t+n,cmp);
        
    int sum=0;//總共需要的會場數(shù)量 
    for(i=0;i<n;i++)//方法2 
    {
        if(!t[i].flag)//找到未安排的活動，進行場地安排 
        {
            sum++;
            int p=i;
            for(j=p+1;j<n;j++)//當前活動結(jié)束時間與下一個活動開始不相交 ，則安排到同一個會場 
            {
                if(t[p].end<=t[j].begin&&!t[j].flag)
                {
                    p=j;t[j].flag=1;
                }
            }
            t[i].flag=1;
        }
    }
    cout<<sum;
    return 0;
}

貪心策略為：把盡可能多的時間互不沖突的活動安排到一個會場，若活動時間交叉，則在安排到另一個會場。

將所有活動按結(jié)束時間升序排列，利用sort函數(shù)，自定義cmp方法。循環(huán)體中，每次可以找到還沒有安排的活動，并以這個活動搜索能同時容納到一個會場的其他活動（這一步嵌套在內(nèi)層循環(huán)中），經(jīng)過兩層循環(huán)，把所有活動全部安排好，這時也已經(jīng)計算出需要的會場數(shù)量sum。

類似的問題是區(qū)間選點

7-10 選點問題 (15 分)

數(shù)軸上有n個閉區(qū)間[ai, bi]。取盡量少的點，使得每個區(qū)間內(nèi)都至少有一個點（不同區(qū)間內(nèi)含的點可以是同一個）。

輸入格式:

第一行一個數(shù)字n，表示有n個閉區(qū)間。下面n行，每行包含2個數(shù)字，表示閉區(qū)間[ai, bi]

輸出格式:

一個整數(shù)，表示至少需要幾個點

輸入樣例:

在這里給出一組輸入。例如：

輸出樣例:

在這里給出相應的輸出。例如：2

開始想找出幾個區(qū)間共同段，并且記錄每個共同段中包含哪些區(qū)間，這樣算出最少選點。后來發(fā)現(xiàn)覺得這個想法其實可以簡化一下，策略為：以右端為擋板，看看前面是否包含其他區(qū)間，如果是，則不記數(shù)，反之，說明沒有共同段，需要計數(shù)并且移動擋板位置繼續(xù)尋找。貪心策略是選擇區(qū)間右端點，保證能夠包含更大交叉段，選的點最少。

#include<bits/stdc++.h>
using namespace std;
struct dot{
    int l,r;
    bool v[10001];
}dots[10001];
int cmp(const dot &a,const dot &b)//比較規(guī)則，按區(qū)間右端點升序排列 
{
    return a.r<b.r;
} 
int main()
{
    int n,i,j,count=1,select;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>dots[i].l>>dots[i].r;
    sort(dots,dots+n,cmp);//預處理，將區(qū)間按規(guī)則排好序，方便后續(xù)比較 
    select=dots[0].r;
    //貪心策略是選擇區(qū)間右端點，保證能夠包含更大交叉段，選的點最少 
    for(i=1;i<n;i++)//每次將當前選擇的一個區(qū)間的右端點與下一個（或者同一區(qū)間，可忽略）左端比較 
    {
        if(dots[i].l>select)//如果沒有交叉，選點+1,并以此區(qū)間右端為新一輪比較的點 
        {
            count++;
            select=dots[i].r;
        }
    }
    cout<<count;
    return 0;
}

上述就是小編為大家分享的c++中的貪心算法的實現(xiàn)方法了，如果您也有類似的疑惑，不妨參照上述方法進行嘗試。如果想了解更多相關(guān)內(nèi)容，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊。

分享名稱：c++中的貪心算法怎么實現(xiàn)-創(chuàng)新互聯(lián)
網(wǎng)頁鏈接：http://muchs.cn/article8/dejcop.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、網(wǎng)站營銷、自適應網(wǎng)站、定制開發(fā)、搜索引擎優(yōu)化、移動網(wǎng)站建設

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容