首页 > 试题广场 >

某酒店会议厅经理需要一个会议排程算法,对每天 个会议室租赁

[问答题]

某酒店会议厅经理需要一个会议排程算法,对每天 个会议室租赁申请进行排程,每个租赁请求的信息为 ,分别表示第 个租赁请求的起始时间、终止时间和租金,其目的是在租赁请求时间不冲突的情况下,获得最多租金,即确定 不冲突,且 最大。请用动态规划方法为其设计一个算法,要求: ,租赁请求

1 写出递归表达式,并加以解释;

2) 根据递归表达式用伪代码写出算法;

更简单的问题: CLRS P414(为什么按完成时间排序)
动态转移方程
table[i]=max(table[i-1],table[IndexCanPut(i)])
table[i]表示只考虑前i+1项会议时的最大收益
用 meetings 存储会议数据

以下是 c++ 实现
#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);
}

关于IndexCanPut函数的解释:
假设table[10]对应的最佳排程方案是
会议1->会议5->会议7
那么table[10]=table[7],因此不用担心
编辑于 2019-01-05 17:48:25 回复(0)