[UVA][烏龜塔][Greedy解] 10154 - Weights and Measures
101 101
100 201
99 300
98 301
5 302
10 50
100 120
10 1000
20 1000
30 40
3 5
2 4
1 2
1 1
10 40
20 100
30 40
Sample Output:
4
2
3
3
3
請容許上面抽像輸入格式，以上幾筆會比較有問題，在此先提出來。
為什麼再次討論這個題目，因為我的演算法特別期中考，考了這一道題目，先說說這兩個問題是等價的。
以下是我初略地想要證明。
給定多個工作的 (deadline, time)，求能安排的最多個數。
(1) 對 max(deadline-time) 的Greedy是錯誤的?
(2) 對 min(time) 的Greedy 是錯誤的?
解決：
(1) 由定理t1+t2+t3 … +tk <= dk ，猜想由於 t1+t2+t3 … +tk-1 <= dk - tk，因此可以揣測 max(d*-t*)，每次挑最大的出來，放入最佳解的解集合S中，為什麼這想法會錯，因為沒有考慮到 t 的效應，是最大的可能會導致個數下降。
I.
只能放入集合首的反例 (4,9)
(6,10)
初始集合 S = {
}，第一步放入 (4,9)，得 S = {(4,9)}，第二步無法放入
(6,10) 因為 6+4 > 9。
最佳解 S = {(4,9),(6,10)}
II.
只能放入集合尾的反例
(4,10) (6,9)
初始集合 S = {
}，第一步放入
(4,10)，得 S = {(4,10)}，第二步無法放入 (6,9)
因為 4+6 > 9
最佳解 S = {(4,10),(6,9)}
III.
可以插入隨機位子的反例
(3,15) (2,12) (6,15) (3,10) (1,8) (1,7) (1,6) (1,5) (1,4) (1,3) (1,2)
初始集合 S = {
}，第一步放入(3,15)，得S = {(3,15)}，第二步放入(2,12)，得S = {(2,12)(3,15)}，第三步放入(6,15)，得S = {(2,12)(6,15)(3,15)}，第四步放入(3,10)，得{(3,10)(2,12)(6,15)(3,15)}，第五步放入(1,8)，得S
={(1,8)(3,10)(2,12)(6,15)(3,15)}，行程滿
1+3+2+6+3 = 15 <= 15。
最佳解 S = {(1,2)(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(3,10),(2,12),(3,15)}
(2) 策略 min(t*) 逐漸放入最佳解之中。
I.
只能放入集合首的反例 (10,40)
(20,100) (30,40)
初始集合 S = {
}，第一步放入 (10,40)，得 S = {(10,40)}，第二步放入(20,100)，得S = {(20,100),(10,40)}，第三步無法放入(30,40)，因為30+20+10
> 40。
最佳解 S = {(30,40),(10,40),(20,100)}
II.
只能放入集合尾的反例 (10,100)
(20,100) (30,40)
初始集合 S = {
}，第一步放入
(10,100)，得 S = {(10,100)}，第二步放入(20,100)，得S = {(10,100),(20,100)}，第三步無法放入(30,40)，因為10+20+30
> 40。
最佳解 S = {(30,40),(10,100),(20,100)}
III.
可以插入隨機位子的反例
目前找不到
後來策略 min(t*) 發現是正確的做法，為什麼正確？因為如果不把最小值放入其中，可以得到一個最優解，那麼必然存在同樣個數的最優解可以把最小值放入，那麼可以斷定最小值一定存在最優集中。
然後 UVa 的測資不夠強，也只不過一測測資，因此我很不信邪地繼續拿我的代碼進行數五萬筆的嘗試，試圖從比較 greedy 和 dp 的作法中，找到一個是錯的，但後來發現找不到。
請容許我不會證明。
#include <stdio.h>
#include <algorithm>
using namespace std;
struct TURTLE {
int w, s; //<weight, strength>
};
int cmp(TURTLE a, TURTLE b) {
if(a.w != b.w)
return a.w < b.w; // weight small->large
return a.s < b.s;
}
int main() {
int n = 0, i, j;
int Ssum, Sn = 0; //total weight
TURTLE S[5700]; //<optimal solution>
TURTLE T[5700];
while(scanf("%d %d", &T[n].w, &T[n].s) == 2)
n++;
sort(T, T+n, cmp);
for(i = 0; i < n; i++) {
if(Sn == 0) {
S[Sn++] = T[i];
continue;
}
for(j = 0, Ssum = 0; j < Sn; j++)
Ssum += S[j].w;
int ins_pos = -1;
for(j = Sn-1; j >= -1; j--) {
if(j+1 == Sn || Ssum + T[i].w <= S[j+1].s) {
if(j+1 != Sn)
Ssum -= S[j+1].w;
if(Ssum + T[i].w <= T[i].s) {
if(j+1 == Sn || S[j+1].s >= T[i].s) {
ins_pos = j+1;
//printf("%d %d\n", i, ins_pos);
}
}
} else
break;
}
if(ins_pos != -1) {
for(j = Sn-1; j >= ins_pos; j--)
S[j+1] = S[j];
S[ins_pos] = T[i];
Sn++;
/*for(j = 0; j < Sn; j++)
printf("(%d, %d)", S[j].w, S[j].s);
puts("");*/
}
}
printf("%d\n", Sn);
return 0;
}