某酒店会议厅经理需要一个会议排程算法,对每天 个会议室租赁申请进行排程,每个租赁请求的信息为 ,分别表示第 个租赁请求的起始时间、终止时间和租金,其目的是在租赁请求时间不冲突的情况下,获得最多租金,即确定 , 和 不冲突,且 最大。请用动态规划方法为其设计一个算法,要求: ,租赁请求
1 ) 写出递归表达式,并加以解释;
2) 根据递归表达式用伪代码写出算法;
table[i]=max(table[i-1],table[IndexCanPut(i)])
#include<iostream> #include<vector> #include<algorithm> using namespace std; struct meeting{ int st,fi,profit; }; typedef vector<meeting> meet_arr; int IndexCanPut(meet_arr &arr,int i){ for(int j=i-1;j>=0;j--){ if(arr[j].fi<=arr[i].st) return j; //arr[i]能放在哪些arr[j]后面?,返回最大的j } return -1; } int meet_sort(meet_arr &arr){ int N =arr.size(); //按完成时间排序 sort(begin(arr),end(arr),[](auto a,auto b){return a.fi<b.fi;}); vector<int> table(N); table[0]=arr[0].profit; for(int i=1;i<N;i++){ int inc_profit = arr[i].profit; int l = IndexCanPut(arr,i); if(l!=-1) inc_profit += table[l]; table[i]=max(inc_profit, table[i-1]); } return table[N-1]; } int main(){ meet_arr meetings{{3,10,20},{1,2,50},{6,19,100},{2,100,200}}; cout<<meet_sort(meetings); }