有一台机器,上面有m个储存空间。然后有n个请求,第i个请求计算时需要占 R[i]个空间,储存计算结果则需要占据O[i]个空间(据O[i]个空间(其中O[i]<R[i])。问怎么安排这n个请求的顺序,使得所有请求都能完成。你的算法也应该能够判断出无论如何都不能处理完的情况。
比方说,m=14,n=2,R[1]=10,O[1]=5,R[2]=8,O[2]=6。在这个例子中,我们可以先运行第一个任务,剩余9个单位的空间足够执行第二个任务;但如果先走第二个任务,第一个任务执行时空间就不够了,因为10>14-6。
//请求数 #define N 2 //存储空间 #define M 14 typedef struct request { int no; int r; int o; } REQ; void printReqs(REQ* reqs, int len) { for (int i = 0; i < len - 1; ++i) { cout << reqs[i].no << "->"; } cout << reqs[len - 1].no << endl; } int cmp(const void* req1, const void* req2) { return (((const REQ*) req2)->r - ((const REQ*) req2)->o) - (((const REQ*) req1)->r - ((const REQ*) req1)->o); } //获取处理完所有请求所需的存储空间 int getAllOccupy(REQ* reqs, int len) { int sum = 0; for (int i = 0; i < len; ++i) { sum += reqs[i].o; } return sum; } bool arrangeDealRequest(REQ* reqs, int len) { if (!reqs || !len) { return false; } int occupy = getAllOccupy(reqs, len); //必定不满足的情况: 处理完所有请求后所需空间小于指定空间 if (M < occupy) { cout << "存储空间不足!!!"; return false; } else { int curSpace = M; //按照R[i]-O[i]的值降序排序 qsort(reqs, len, sizeof(REQ), cmp); for (int i = 0; i < len; ++i) { if (curSpace >= reqs[i].r) { curSpace -= reqs[i].o; } else { cout << "运行空间不足!!!"; return false; } } return true; } }