Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Sample Input:
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)   由定理t₁+t₂+t₃ … +t_k <= d_k ，猜想由於 t₁+t₂+t₃ … +t_k-1 <= d_k - t_k，因此可以揣測 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;
}