學習演算法課程之後的第一次記錄,漸漸的,程式設計考慮的因素增多,程式=資料結構 演算法,這個等式讓我深有體會。從開始簡單的C 編程,再到選擇合適資料結構,現在需要更進一步,從演算法層次考慮程式執行的效率。我對演算法的理解是用更少的開銷來獲得更優的執行效果。
分治法、動態規劃在此之前沒有記錄下來,學到貪心演算法的時候,覺得需要總結一下學過的東西,也能更好的理解。動態規劃的設計,要滿足最優子結構性質和重疊子問題,採用自底向上的策略,計算出最優值,找出整體最優解。這個過程有時候挺難的,主要在寫出遞歸式,要自底向上填表。貪心策略有點像動態規劃,但在某些方面是不同的,有時候貪心演算法的想法更容易想到。它要滿足子問題最優而得到整體最優?兩個條件:最優子結構性質和貪心選擇性質。滿足貪心選擇性質一定滿足最優子結構性質,而滿足最優子結構性質不一定滿足貪心選擇性質,例如背包問題可以用貪心演算法解決,而0-1背包問題只能用動態規劃。
典型的貪心問題活動安排,有n個活動,給出開始時間和結束時間,要盡可能安排多的活動(時間互相不衝突)。解決這個問題正確的貪心思想是以每個活動結束時間為比較變量,按結束時間升序排好活動次序,接著就進行比較選擇。而會場安排問題與活動又有些不同之處,以下是我的解題過程。
7-2 會場安排問題 (20 分)
假設要在足夠多的會場里安排一批活動,並希望使用盡可能少的會場。設計一個有效的 貪心演算法進行安排。 (這個問題其實是著名的圖著色問題。若將每一個活動作為圖的一個頂點,不相容活動間用邊相連。使相鄰頂點著有不同顏色的最小著色數,對應於要找的最小會場數。)
輸入格式:
第一行有1 個正整數k,表示有k個待安排的活動。接下來的 k行中,每行有 2個正整數,分別表示 k個待安排的活動開始時間和結束時間。時間 以 0 點開始的分鐘計。
輸出格式:
輸出最少會場數。
輸入範例:
5 1 23 12 28 25 35 27 80 36 50
輸出範例:
3
#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)//比较规则:以结束时间升序排列 { 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;//总共需要的会场数量 for(i=0;i<n;i++)//方法2 { if(!t[i].flag)//找到未安排的活动,进行场地安排 { sum++; int p=i; for(j=p+1;j<n;j++)//当前活动结束时间与下一个活动开始不相交 ,则安排到同一个会场 { if(t[p].end<=t[j].begin&&!t[j].flag) { p=j;t[j].flag=1; } } t[i].flag=1; } } cout<<sum; return 0; }
貪心策略為:把盡可能多的時間互不衝突的活動安排到一個會場,若活動時間交叉,則在安排到另一個會場。
將所有活動依結束時間升序排列,利用sort函數,自訂cmp方法。循環體中,每次可以找到還沒有安排的活動,並以這個活動搜尋能同時容納到一個會場的其他活動(這一步嵌套在內層循環中),經過兩層循環,把所有活動全部安排好,這時也已經計算出需要的會場數sum。
類似的問題是區間選點
7-10 選點問題(15 分)
數軸上有n個閉區間[ai , bi]。取盡量少的點,使得每個區間內都至少有一個點(不同區間內含的點可以是同一個)。
輸入格式:
第一行一個數字n,表示有n個閉區間。下面n行,每行包含2個數字,表示閉區間[ai, bi]
輸出格式:
一個整數,表示至少需要幾個點
輸入範例:
在這裡給出一組輸入。例如:
3 1 3 2 4 5 6
輸出範例:
在這裡給出對應的輸出。例如:2
開始想找出幾個區間共同段,並且記錄每個共同段包含哪些區間,這樣算最少選點。後來發現覺得這個想法其實可以簡化一下,策略為:以右端為擋板,看看前面是否包含其他區間,如果是,則不記數,反之,說明沒有共同段,需要計數並且移動擋板位置繼續尋找。貪心策略是選擇區間右端點,保證能包含更大交叉段,選的點最少。
#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)//比较规则,按区间右端点升序排列 { 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);//预处理,将区间按规则排好序,方便后续比较 select=dots[0].r; //贪心策略是选择区间右端点,保证能够包含更大交叉段,选的点最少 for(i=1;i<n;i++)//每次将当前选择的一个区间的右端点与下一个(或者同一区间,可忽略)左端比较 { if(dots[i].l>select)//如果没有交叉,选点+1,并以此区间右端为新一轮比较的点 { count++; select=dots[i].r; } } cout<<count; return 0; }
學習演算法之後,發現解決問題上需要思考上的改變,程式設計之前的演算法選擇很重要,還要向大佬們學習,典型演算法的學習研究真是博大精深呀!
本文來自 C#.Net教學 欄目,歡迎學習!
以上是c++貪心演算法(會場安排、區間選點)範例的詳細內容。更多資訊請關注PHP中文網其他相關文章!