作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 一个感觉是 dynamic programming 的题目
时间Fri Apr 23 12:06:05 2010
l大所写的演算法是有来源的。
寄信询问l大之後，得到的回覆，整理於下。
最早出现的文献
Moore, J.M.(1968) An n job, one machine sequencing algorithm
for minimizing the number of late jobs. Management Science.
15(1):102-109.
现在的演算法名称
Moore-Hodgson Algorithm
时间复杂度
O(N * log(N))
演算法证明
(1)先证至少有一最佳解工作顺序是依完工期限由小到大排
(2)证明拿掉最大执行时间的工作不会比最佳解差
问题转换方式
Instance: 有n个工作要完成 <---> 有n个箱子要叠
每个工作有不同的处理时间 <---> 不同的重量
每个工作有不同的完工期限 <---> 不同的载重量(要包含自己重量)
Question: 让无法如期完工的工作越少越好 <---> 箱子叠越多越好
C++实作
1. struct Job {int time, due;} job[10];
2.
3. bool cmp(const Job& j1, const Job& j2)
4. {
5. return j1.due < j2.due;
6. }
7.
8. void Moore_Hodgson()
9. {
10. sort(job, job+10, cmp);
11.
12. int t = 0;
13. priority_queue<int> pq;
14. for (int i=0; i<10; ++i)
15. {
16. pq.push(job[i].time);
17. t += job[i].time;
18. if (t > job[i].due) t -= pq.top(), pq.pop();
19. }
20.
21. cout << "如期完成的工作(箱子)数目，最多为" << pq.size();
22. }
-
个人觉得，这个问题整理成这样，都可以出论文了。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.115.154.181
※ 编辑: DJWS 来自: 59.115.154.181 (04/23 12:16)
※ 编辑: DJWS 来自: 59.115.154.181 (04/23 12:28)
※ 编辑: DJWS 来自: 59.115.154.181 (04/23 12:37)