解題區/解題區 - UVa

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();
}