作者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)