C++與Java分別解決活動(dòng)選擇問題和帶權(quán)活動(dòng)選擇問題
貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮,它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。
活動(dòng)安排問題
問題描述: 設(shè)有n個(gè)活動(dòng)的集合E = {1,2,…,n},其中每個(gè)活動(dòng)都要求使用同一資源,如演講會(huì)場(chǎng)等,而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si < fi 。如果選擇了活動(dòng)i,則它在半開時(shí)間區(qū)間[si, fi)內(nèi)占用資源。若區(qū)間[si, fi)與區(qū)間[sj, fj)不相交,則稱活動(dòng)i與活動(dòng)j是相容的。也就是說,當(dāng)si >= fj或sj >= fi時(shí),活動(dòng)i與活動(dòng)j相容。
活動(dòng)選擇問題代碼實(shí)現(xiàn)
#include <iostream> #include <vector> #include <algorithm> using namespace std ; struct ActivityTime { public: ActivityTime (int nStart, int nEnd) : m_nStart (nStart), m_nEnd (nEnd) { } ActivityTime () : m_nStart (0), m_nEnd (0) { } friend bool operator < (const ActivityTime& lth, const ActivityTime& rth) { return lth.m_nEnd < lth.m_nEnd ; } public: int m_nStart ; int m_nEnd ; } ; class ActivityArrange { public: ActivityArrange (const vector<ActivityTime>& vTimeList) { m_vTimeList = vTimeList ; m_nCount = vTimeList.size () ; m_bvSelectFlag.resize (m_nCount, false) ; } // 活動(dòng)安排 void greedySelector () { __sortTime () ; // 第一個(gè)活動(dòng)一定入內(nèi) m_bvSelectFlag[0] = true ; int j = 0 ; for (int i = 1; i < m_nCount ; ++ i) { if (m_vTimeList[i].m_nStart > m_vTimeList[j].m_nEnd) { m_bvSelectFlag[i] = true ; j = i ; } } copy (m_bvSelectFlag.begin(), m_bvSelectFlag.end() ,ostream_iterator<bool> (cout, " ")); cout << endl ; } private: // 按照活動(dòng)結(jié)束時(shí)間非遞減排序 void __sortTime () { sort (m_vTimeList.begin(), m_vTimeList.end()) ; for (vector<ActivityTime>::iterator ite = m_vTimeList.begin() ; ite != m_vTimeList.end() ; ++ ite) { cout << ite->m_nStart << ", "<< ite ->m_nEnd << endl ; } } private: vector<ActivityTime> m_vTimeList ; // 活動(dòng)時(shí)間安排列表 vector<bool> m_bvSelectFlag ;// 是否安排活動(dòng)標(biāo)志 int m_nCount ; // 總活動(dòng)個(gè)數(shù) } ; int main() { vector<ActivityTime> vActiTimeList ; vActiTimeList.push_back (ActivityTime(1, 4)) ; vActiTimeList.push_back (ActivityTime(3, 5)) ; vActiTimeList.push_back (ActivityTime(0, 6)) ; vActiTimeList.push_back (ActivityTime(5, 7)) ; vActiTimeList.push_back (ActivityTime(3, 8)) ; vActiTimeList.push_back (ActivityTime(5, 9)) ; vActiTimeList.push_back (ActivityTime(6, 10)) ; vActiTimeList.push_back (ActivityTime(8, 11)) ; vActiTimeList.push_back (ActivityTime(8, 12)) ; vActiTimeList.push_back (ActivityTime(2, 13)) ; vActiTimeList.push_back (ActivityTime(12, 14)) ; ActivityArrange aa (vActiTimeList) ; aa.greedySelector () ; return 0 ; }
結(jié)果
帶權(quán)活動(dòng)選擇問題
算法偽代碼【核心算法】
問題描述:
會(huì)場(chǎng)出租:選擇出租的活動(dòng)時(shí)間不能沖突,怎樣選擇才能選更多的活動(dòng)?
帶權(quán)活動(dòng)選擇問題代碼實(shí)現(xiàn)
package day1.java; public class activityChoose { private static class Activity{ int startTime; int endTime; int weight; private Activity(int startTime, int endTime, int weight){ this.startTime = startTime; this.endTime = endTime; this.weight = weight; } } private static void activityChoose(Activity[] S){ // 記錄p:在a_i開始前最后結(jié)束的活動(dòng) int[] p = new int[S.length+1]; p[0] = 0; p[1] = 0; for(int i=2; i<=S.length; i++){ for(int j=i-1; j>0; j--){ if(S[j-1].endTime <= S[i-1].startTime){ p[i] = j; break; } } } for(int i=1; i<=S.length; i++){ System.out.println(p[i]); } int[] D = new int[S.length+1]; int[] Rec = new int[S.length+1]; D[0] = 0; // 動(dòng)態(tài)規(guī)劃 for(int j=1; j<S.length+1; j++){ if(D[p[j]]+S[j-1].weight > D[j-1]){ D[j] = D[p[j]] + S[j-1].weight; Rec[j] = 1; }else{ D[j] = D[j-1]; Rec[j] = 0; } } // 輸出方案 int k=S.length; while(k > 0){ if(Rec[k] == 1){ System.out.println("選擇:開始時(shí)間"+S[k-1].startTime+"結(jié)束時(shí)間"+S[k-1].endTime); k = p[k]; }else{ k--; } } } // 按結(jié)束時(shí)間從小到大排序 private static void quickSortActivity(Activity[] S, int start, int end){ int i = start; int j = end; if (start < end){ Activity tmp = S[i]; while(i<j){ while(i<j && S[i].endTime <= S[j].endTime){ j--; } S[i] = S[j]; while (i < j && S[i].endTime >= S[j].endTime) { i++; } S[j] = S[i]; } S[i] = tmp; quickSortActivity(S, start, i-1); quickSortActivity(S, i+1,end); } } public static void main(String[] args){ Activity[] S = new Activity[10]; S[0] = new Activity(1,4,1); S[1] = new Activity(3,5,6); S[2] = new Activity(0,6,4); S[3] = new Activity(4,7,7); S[4] = new Activity(3,9,3); S[5] = new Activity(5,9,12); S[6] = new Activity(6,10,2); S[7] = new Activity(8,11,9); S[8] = new Activity(8,12,11); S[9] = new Activity(2,14,8); quickSortActivity(S, 0, 9); activityChoose(S); } }
結(jié)果
到此這篇關(guān)于C++與Java分別解決活動(dòng)選擇問題和帶權(quán)活動(dòng)選擇問題的文章就介紹到這了,更多相關(guān)C++活動(dòng)選擇內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++實(shí)現(xiàn)LeetCode(75.顏色排序)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(75.顏色排序),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07

實(shí)例講解C語言編程中的結(jié)構(gòu)體對(duì)齊

如何用C++制作LeetCode刷題小技巧-錯(cuò)題記錄本

C++中CSimpleList的實(shí)現(xiàn)與測(cè)試實(shí)例

C++構(gòu)造函數(shù)深度學(xué)習(xí)

C語言中動(dòng)態(tài)內(nèi)存分配malloc、calloc和realloc函數(shù)解析