問題背景：

所謂“鐘點秘書”，是指年輕白領(lǐng)女性利用工余時間為客戶提供秘書服務(wù)，并按鐘點收取酬金。“鐘點秘書”為客戶提供有償服務(wù)的方式一般是：采用電話、電傳、上網(wǎng)等“遙控”式
服務(wù)，或親自到客戶公司處理部分業(yè)務(wù)。其服務(wù)對象主要有三類：一是外地前來考察商務(wù)經(jīng)營、項目投資的商人或政要人員，他們由于初來乍到，急需有經(jīng)驗和熟悉本地情況的秘書幫忙；二是前來開展短暫商務(wù)活動，或召開小型資訊發(fā)布會的國外客商；三是本地一些請不起長期秘書的企、事業(yè)單位。這些客戶普遍認(rèn)為：請“鐘點秘書”，一則可免去專門租樓請人的大筆開銷；二則可根據(jù)開展的商務(wù)活動請有某方面專長的可用人才；三則由于對方是臨時雇用關(guān)系，工作效率往往比固定的秘書更高。據(jù)調(diào)查，在上海“鐘點秘書”的行情日趨看好。對此，業(yè)內(nèi)人士認(rèn)為：為了便于管理，各大城市有必要組建若干家“鐘點秘書服務(wù)公司”，通過會員制的形式，為眾多客戶提供規(guī)范、優(yōu)良、全面的服務(wù)，這也是建設(shè)國際化大都市所必需的。某跨國公司總裁正分身無術(shù)，為一大堆會議時間表焦頭爛額，希望高級鐘點秘書能做出合理的安排，能在有限的時間內(nèi)召開更多的會議。

問題分析：

這是一個典型的會議安排問題，會議安排的目的是能在有限的時間內(nèi)召開更多的會議
（任何兩個會議不能同時進行）。在會議安排中，每個會議 i 都有起始時間 bi 和結(jié)束時間 ei，且 bi<ei，即一個會議進行的時間為半開區(qū)間[bi，ei）。如果[bi，ei）與[bj，ej）均在“有限的時間內(nèi)”，且不相交，則稱會議 i 與會議 j 相容的。也就是說，當(dāng) bi≥ej 或 bj≥ei 時，會議 i與會議 j 相容。會議安排問題要求在所給的會議集合中選出最大的相容活動子集，即盡可能在有限的時間內(nèi)召開更多的會議。在這個問題中，“有限的時間內(nèi)（這段時間應(yīng)該是連續(xù)的）”是其中的一個限制條件，也應(yīng)該是有一個起始時間和一個結(jié)束時間（簡單化，起始時間可以是會議最早開始的時間，結(jié)束時間可以是會議最晚結(jié)束的時間），任務(wù)就是實現(xiàn)召開更多的滿足在這個“有限的時間內(nèi)”等待安排的會議。

算法設(shè)計：

（1）初始化：將 n 個會議的開始時間、結(jié)束時間存放在結(jié)構(gòu)體數(shù)組中（想一想，為什么
不用兩個一維數(shù)組分別存儲？），如果需要知道選中了哪些會議，還需要在結(jié)構(gòu)體中增加會議編號，然后按結(jié)束時間從小到大排序（非遞減），結(jié)束時間相等時，按開始時間從大到小排序（非遞增）；
（2）根據(jù)貪心策略就是選擇第一個具有最早結(jié)束時間的會議，用 last 記錄剛選中會議的
結(jié)束時間；
（3）選擇第一個會議之后，依次從剩下未安排的會議中選擇，如果會議 i 開始時間大于
等于最后一個選中的會議的結(jié)束時間 last，那么會議 i 與已選中的會議相容，可以安排，更新 last 為剛選中會議的結(jié)束時間；否則，舍棄會議 i，檢查下一個會議是否可以安排。

通俗講：先將數(shù)據(jù)存到結(jié)構(gòu)體中，用結(jié)束時間從小到大排序（若結(jié)束時間相同，以開始時間由大到小排序），之后再次基礎(chǔ)上再判斷開始時間；在會議按結(jié)束時間非遞減排序的基礎(chǔ)上，首先選中第一個會議，用 last 變量記錄剛剛被選中會議的結(jié)束時間。下一個會議的開始時間與 last 比較，如果大于等于 last，則選中。每次選中一個會議，更新 last 為最后一個被選中會議的結(jié)束時間，被選中的會議數(shù)counter加 1；如果會議的開始時間不大于等于 last，繼續(xù)考查下一個會議，直到所有會議考查完畢。最后返回counter即可；

樣例輸入：

10//10個會議
3 6 //開始時間 結(jié)束時間
1 4
5 7
2 5
5 9
3 8
8 11
6 10
8 12
12 14

樣例輸出：

4

代碼如下：

#include <iostream> #include<stdio.h> #include<algorithm> using namespace std;struct meet{//用結(jié)構(gòu)體存儲會議int begin1;//會議開始時間int end1;//輝夜結(jié)束時間int number;//會議編號 }a[1014];bool beyond(meet a,meet b){//按結(jié)束時間由早到晚排序if(a.end1 == b.end1) return a.begin1>b.begin1;//若結(jié)束時間相同，會議開始時間由晚到早排序return a.end1<b.end1; }int main() {int all;//總會議數(shù)int last;int counter=1;scanf("%d",&all);for(int i=0;i<all;i++){scanf("%d",&a[i].begin1);scanf("%d",&a[i].end1);a[i].number = i+1;//會議編號}sort(a,a+all,beyond);//會議結(jié)束時間由早到晚排序last = a[0].end1;//這里的last為結(jié)束最早的會議結(jié)束時間for(int j=1;j<all;j++){if(a[j].begin1 >= last){//然后找另一個比這個會議結(jié)束時間大的開始時間的會議counter ++;last = a[j].end1;}}printf("%d",counter);return 0; }

總結(jié)

以上是生活随笔為你收集整理的0-1背包问题（物品不可分割）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。