Re: [問題] 一個感覺是 dynamic programming 的題目

看板Prob_Solve (計算數學 Problem Solving)作者 (...)時間14年前 (2010/04/23 12:06), 編輯推噓0(000)
留言0則, 0人參與, 最新討論串11/12 (看更多)
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)
文章代碼(AID): #1BqHom5S (Prob_Solve)
討論串 (同標題文章)
文章代碼(AID): #1BqHom5S (Prob_Solve)