UVa 10154 - Weights and Measures

contents

曾經紅及一時的的烏龜塔問題,討論相當多。最近學弟因為 2014 年資訊奧林匹亞研習營初選中的一題,跑來問我怎麼解比較好。但是想一想之前都是用 dp 過去的。速度 O(n^2),優化也只會是 O(k n),k 是答案,還是還用了貪心去解決,但是後來才挖到這個化石,想法是挺簡單的,人生白活了。

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Job {int time, due;} job[10]; 
bool cmp(const Job& j1, const Job& j2) {
return j1.due < j2.due;
}
void Moore_Hodgson() {
sort(job, job+10, cmp);
int t = 0;
priority_queue<int> pq;
for (int i=0; i<10; ++i) {
pq.push(job[i].time);
t += job[i].time;
if (t > job[i].due) t -= pq.top(), pq.pop();
}
cout << "如期完成的工作(箱子)數目,最多為" << pq.size();
}