九度筆記之 項目安排

題目描述：
小明每天都在開源社區上做項目，假設每天他都有很多項目可以選，其中每個項目都有一個開始時間和截止時間，假設做完每個項目後，拿到報酬都是不同的。由於小明馬上就要碩士畢業了，面臨著買房、買車、給女友買各種包包的鴨梨，但是他的錢包卻空空如也，他需要足夠的money來充實錢包。萬能的網友麻煩你來幫幫小明，如何在最短時間內安排自己手中的項目才能保證賺錢最多（注意：做項目的時候，項目不能並行，即兩個項目之間不能有時間重疊，但是一個項目剛結束，就可以立即做另一個項目，即項目起止時間點可以重疊）。

輸入：
輸入可能包含多個測試樣例。
對於每個測試案例，輸入的第一行是一個整數n(1<=n<=10000)：代表小明手中的項目個數。
接下來共有n行，每行有3個整數st、ed、val，分別表示項目的開始、截至時間和項目的報酬，相鄰兩數之間用空格隔開。
st、ed、value取值均在32位有符號整數（int）的范圍內，輸入數據保證所有數據的value總和也在int范圍內。

輸出：
對應每個測試案例，輸出小明可以獲得的最大報酬。

樣例輸入：
3
1 3 6
4 8 9
2 5 16
4
1 14 10
5 20 15
15 20 8
18 22 12樣例輸出：
16
22算法分析

本題采用回溯法，假定安排了第k個項目後，下一個項目的開始時間肯定在k個項目時間的結束之後。

數據結構

Project
 
 
 
Id
 int
 代表項目名
 
Order
 int
 代表按照項目的開始時間排序後，該項目的序號，從0開始
 
btime
 int
 項目起始時間
 
etime
 int
 項目結束時間
 
pf
 int    
 項目收益
 

在回溯過程中需要查找某個項目的next項目和adjacent項目，為了加快計算速度，所以提前對項目按照開始時間進行排序。

Next項目指某個項目做完後可以接著做的項目

Adjacent項目是指比某個項目開始時間相同或晚一些的項目

現在來講述具體算法流程

void manageP(int curOrder,int curpf,const std::vector<Project>&pv)

pv為已經排好序的項目列表

假定已經安排了幾個項目，最後一個為curOrder(排序序列號), 求得curOrder的Next項目nextOrder

(1)將nextOrder放入計劃。

manageP(nextOrder,curpf+pv.at(nextOrder).pf,pv);

在此要判斷nextOrder是否存在，也就是計劃是否已經滿了，是的話就比較當前的獲益，如果比allpf大，就更新allpf.

(2)不加入nextOrder,而是加入nextOrder的adjacentOrder

manageP(adjacentOrder,curpf+pv.at(adjacentOrder).pf,pv);

在此也要判斷nextOrder是否是最後一個項目，如果是的話就不存在adjacentOrder，計劃已經結束，判斷當前收益是否大於allpf.

我們還需要考慮另外一種情況，adjacentOrder的開始時間>=nextOrder的結束時間

在這種情況下得到的收益肯定不是最大，因為中間可以插入nextOrder項目

代碼

[cpp]
// test1499.cpp : 定義控制台應用程序的入口點。  
//  
 
#include "stdafx.h"  
#include <iostream>  
#include <vector>  
#include <algorithm>  
 
struct Project{ 
    int id; 
    int order;//記錄排序後的位置，便於搜尋下一個項目  
    int btime; 
    int etime; 
    int pf; 
}; 
//std::vector<Project> userp;  
int allpf=0;//盈利  
bool lessthan(const Project &a,const Project &b){ 
    return a.btime < b.btime; 
} 
int getNextP(int curOrder,const std::vector<Project> &pv){//得到和項目cur時間不重疊的下一個項目  
    if(curOrder==-1) 
        return 0; 
    std::vector<Project>::const_iterator cit = pv.begin() + curOrder +1; 
    for(;cit!=pv.end();cit++){ 
        if(cit->btime >= pv.at(curOrder).etime){ 
            return cit->order; 
        } 
    } 
    if(cit==pv.end()){ 
        return -1; 
    } 
} 
/*
int getAdjacentP(const Project &cur, const std::vector<Project> &pv){//得到開始時間在項目cur開始時間之後或重合的下一個項目
    if(cur.order == pv.size()-1)
        return 0;
    else
        return cur.order+1;
}
*/ 
void manageP(int curOrder,int curpf,const std::vector<Project> &pv){//已經加入了k-1個項目，k-1為cur項目  
    //加入  
    int nextOrder; 
    nextOrder = getNextP(curOrder,pv); 
    if(nextOrder==-1){ 
        if(curpf>allpf) 
            allpf = curpf; 
        return; 
    }else{ 
        manageP(nextOrder,curpf+pv.at(nextOrder).pf,pv); 
    } 
 
    if(nextOrder == pv.size()-1){                       //nextOrder是最後一個項目  
        if(curpf+pv.at(nextOrder).pf > allpf){ 
            allpf = curpf+pv.at(nextOrder).pf; 
            return; 
        } 
    }else{ 
        int adjacentOrder = nextOrder+1; 
        if(pv.at(adjacentOrder).btime >= pv.at(nextOrder).etime){  //adjacentOrder開始時間在nextOrder結束時間之後  
            //得到的利潤肯定沒有 加上nextOrder的多  
            return; 
        }else{ 
            manageP(adjacentOrder,curpf+pv.at(adjacentOrder).pf,pv); 
        } 
    } 
 
} 
void test1499(int n){ 
    int i = 0; 
    Project p; 
    std::vector<Project> pv; 
    while(i++<n){ 
        std::cin>>p.btime>>p.etime>>p.pf; 
        p.id = i; 
        p.order = 0; 
        pv.push_back(p); 
    } 
    std::sort(pv.begin(),pv.end(),lessthan); 
    for(std::vector<Project>::size_type st = 0;st<pv.size();st++){ 
        pv.at(st).order = st; 
    } 
 
    manageP(-1,0,pv); 
    std::cout<<allpf<<std::endl; 
} 
 
int _tmain(int argc, _TCHAR* argv[]) 
{ 
    int n =0; 
    while(std::cin>>n){ 
        test1499( n); 
    } 
     
    return 0; 
} 

// test1499.cpp : 定義控制台應用程序的入口點。
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>

struct Project{
 int id;
 int order;//記錄排序後的位置，便於搜尋下一個項目
 int btime;
 int etime;
 int pf;
};
//std::vector<Project> userp;
int allpf=0;//盈利
bool lessthan(const Project &a,const Project &b){
 return a.btime < b.btime;
}
int getNextP(int curOrder,const std::vector<Project> &pv){//得到和項目cur時間不重疊的下一個項目
 if(curOrder==-1)
  return 0;
 std::vector<Project>::const_iterator cit = pv.begin() + curOrder +1;
 for(;cit!=pv.end();cit++){
  if(cit->btime >= pv.at(curOrder).etime){
   return cit->order;
  }
 }
 if(cit==pv.end()){
  return -1;
 }
}
/*
int getAdjacentP(const Project &cur, const std::vector<Project> &pv){//得到開始時間在項目cur開始時間之後或重合的下一個項目
 if(cur.order == pv.size()-1)
  return 0;
 else
  return cur.order+1;
}
*/
void manageP(int curOrder,int curpf,const std::vector<Project> &pv){//已經加入了k-1個項目，k-1為cur項目
 //加入
 int nextOrder;
 nextOrder = getNextP(curOrder,pv);
 if(nextOrder==-1){
  if(curpf>allpf)
   allpf = curpf;
  return;
 }else{
  manageP(nextOrder,curpf+pv.at(nextOrder).pf,pv);
 }

 if(nextOrder == pv.size()-1){                       //nextOrder是最後一個項目
  if(curpf+pv.at(nextOrder).pf > allpf){
   allpf = curpf+pv.at(nextOrder).pf;
   return;
  }
 }else{
  int adjacentOrder = nextOrder+1;
  if(pv.at(adjacentOrder).btime >= pv.at(nextOrder).etime){  //adjacentOrder開始時間在nextOrder結束時間之後
   //得到的利潤肯定沒有 加上nextOrder的多
   return;
  }else{
   manageP(adjacentOrder,curpf+pv.at(adjacentOrder).pf,pv);
  }
 }

}
void test1499(int n){
 int i = 0;
 Project p;
 std::vector<Project> pv;
 while(i++<n){
  std::cin>>p.btime>>p.etime>>p.pf;
  p.id = i;
  p.order = 0;
  pv.push_back(p);
 }
 std::sort(pv.begin(),pv.end(),lessthan);
 for(std::vector<Project>::size_type st = 0;st<pv.size();st++){
  pv.at(st).order = st;
 }

 manageP(-1,0,pv);
 std::cout<<allpf<<std::endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
 int n =0;
 while(std::cin>>n){
  test1499( n);
 }
 
 return 0;
}
[cpp]

id,order成員變量可以去除，新的代碼為

[cpp]
#include "stdafx.h"  
#include <iostream>  
#include <vector>  
#include <algorithm>  
 
struct Project{ 
    //int id;  
    //int order;  
    int btime; 
    int etime; 
    int pf; 
}; 
int allpf=0; 
bool lessthan(const Project &a,const Project &b){ 
    return a.btime < b.btime; 
} 
int getNextP(std::vector<Project>::size_type curOrder,const std::vector<Project> &pv){ 
    if(curOrder==-1) 
        return 0; 
    //std::vector<Project>::const_iterator cit = pv.begin() + curOrder +1;  
    std::vector<Project>::size_type t = curOrder +1; 
    for(; t<pv.size(); t++){ 
        if(pv[t].btime >= pv[curOrder].etime){ 
            return static_cast<int>(t); 
        } 
    } 
    if(t==pv.size()){ 
        return -1; 
    } 
} 
 
void manageP(std::vector<Project>::size_type curOrder,int curpf,const std::vector<Project> &pv){ 
     
    int nextOrder; 
    nextOrder = getNextP(curOrder,pv); 
    if(nextOrder==-1){ 
        if(curpf>allpf) 
            allpf = curpf; 
        return; 
    }else{ 
        manageP(static_cast<std::vector<Project>::size_type>(nextOrder),curpf+pv.at(nextOrder).pf,pv); 
    } 
 
    if(nextOrder == pv.size()-1){                       
        if(curpf+pv.at(nextOrder).pf > allpf){ 
            allpf = curpf+pv.at(nextOrder).pf; 
            return; 
        } 
    }else{ 
        int adjacentOrder = nextOrder+1; 
        if(pv.at(adjacentOrder).btime >= pv.at(nextOrder).etime){   
             
            return; 
        }else{ 
            manageP(static_cast<std::vector<Project>::size_type>(adjacentOrder),curpf+pv.at(adjacentOrder).pf,pv); 
        } 
    } 
 
} 
void test1499(int n){ 
    int i = 0; 
    Project p; 
    std::vector<Project> pv; 
    while(i++<n){ 
        std::cin>>p.btime>>p.etime>>p.pf; 
        //p.id = i;  
        //p.order = 0;  
        pv.push_back(p); 
    } 
    std::sort(pv.begin(),pv.end(),lessthan); 
    /*
    for(std::vector<Project>::size_type st = 0;st<pv.size();st++){
        pv.at(st).order = st;
    }
    */ 
    manageP(-1,0,pv); 
    std::cout<<allpf<<std::endl; 
} 
 
int _tmain(int argc, _TCHAR* argv[]) 
{ 
    int n =0; 
    while(std::cin>>n){ 
        test1499( n); 
    } 
     
    return 0; 
}