2008年11月10日 星期一

UVa 103 Stacking Boxes

題目講解

這題給你一堆多維的箱子,要找出最長的裝箱序列,這個最常裝箱序列就是像俄羅斯娃娃那樣,大箱子裡面放入小箱子,一層包一層,必須要可以裝最多層這樣。

這題的麻煩就是各個箱子之間不一定有的大小關係 (數學上打這叫偏序集 Partial Order Set ,不過這兒我們先不管 ),比方說有兩個三維箱子 BoxA(1,4,5) 、BoxB(2,4,6) ,B箱比較大,所以 BoxA 可以裝進 BoxB 裡,那麼我們說 BoxA < BoxB 。

但來看 BoxC(1,5,6) 跟 BoxD (2,4,5) 呢? 我們既不能說BoxC < BoxD ,也不能說 BoxC > BoxD,BoxC 與 BoxD 兩者之間就沒有大小關係。

一個簡單的表示法就是有向圖(Directed Graph)
比如說 A(1,2,3) B(2,4,6) C(2,3,7) D(50,50,50) E(10,10,100) 的有向圖表示法:



到此為止,本題的最長裝箱序列,已經有兩種解法,第一個方法就是找圖的最長路徑,稍微修改 Warsahll algorithm 來解,第二個方法是跑 LIS 。

我這裡用 LIS(最長上昇子串列) 解法。

//先定義一個box struct
struct Box {
    int no;
    int edge[10];
};

Box box[30]; 

LIS 法的關鍵是要先對箱子排序,確保小箱子一定在大箱子前,至於沒有大小關係箱子的就隨便放沒關係。這個排序以圖的角度是拓樸排序,以字串的角度是字典排序,兩者都行。

sort(box[i].edge) for all i  //先對箱子內部的邊長排序

int lexico_less(const Box& a, const Box& b) {
    for(int i=0;i<dimension;++i)
        if( !(a.edge[i]<=b.edge[i]) )
            return false;
    return true;
}
sort(box) by lexico_less(); //再用字典序排箱子
一切都準備好後,就可以直接套用LIS解了。
// LIS
int length[MAX_BOX];
int   prev[MAX_BOX];

length[i] = 1  for all i;
  prev[i] = -1 for all i;

for(int i=0;i<num_box;++i)
    for(int j=i+1;j<num_box;++j) {
        if( box[i]<box[j] ) {
            if(length[i]+1 > length[j] ){
                length[j] = length[i]+1;
                prev[j] = i;
            }
        }
    }
輸出結果
int max = max_element(length, length+num_box) - length;
    //print the result
    printf("%d\n", length[max]);

    int output_seq[MAX_BOX];
    int size = 0;

    int cur = max;
    do {
        output_seq[size++] = box[cur].no;
        cur = prev[cur];
    } while( cur!= -1 );

    for(int i=size-1;i>0;--i)
        printf("%d ", output_seq[i]);
    printf("%d\n", output_seq[0]);
}

碎碎念

值得慶賀的事,Ranking 進世界百大!!!! 我相信這是誤打誤撞XDDD,不過真的蠻爽的。 @2008.11.10

6 則留言:

  1. 好像蠻多DP題都可以化成圖來做
    不過這題我還是用LIS
    不過時間複雜度很難算倒是真的
    上網找解答的時候
    才發現有人的寫法跟我一樣奇怪XDD

    回覆刪除
  2. 小弟正在寫acm 103題,但是卡了一陣子,實在想不到什麼好方法寫,是不是可以指點一下你解題的概念,雖然有程式碼,但是我對你使用的語言不很熟,謝謝

    回覆刪除
  3. 我想千言萬語不如一個好的方向
    試著去搜尋 LIS算法(最長上升子序列)

    這題的程式碼在下我自己都看得很心虛呀,寫得亂七八糟

    回覆刪除
  4. 其實這題不用DP

    用greedy也可以AC

    回覆刪除
  5. 用greedy也能AC是因為測資薄弱,不夠有鑑別力,其實greedy作法是有缺陷的。

    回覆刪除
  6. 感謝題解~有向圖的思維沒想到
    請問一下
    int lexico_less(const Box& a, const Box& b)
    這個排出來是照可不可以放入吧?
    字典排序不是a.edge[i]<b.edge[i])

    回覆刪除