瑞の資訊備忘錄

一、目的： 在數學及計算機科學中某些觀念在一維或二維是很簡單，但是當擴展至任意維度時將會

              變的很複雜。例如解決數個維度中的不同方程式和分析n維度立方體的拓撲等問題；但是

              由於後者在不同的維度之間存在著一個明顯的關係，因此前者在高維度時比後者還要複雜。

              (連結UVa online原文題庫)

二、問題說明：

        多維度箱子的收納問題是如何讓一系列同維度但不同大小的箱子進行最大巢狀收納的方法。

        而在進行巢狀收納時有下列條件及規則：

                1、維度內的數值可以任意的對調。 EX: (2,6) => (6,2)

                2、排序後外部箱子中同位置的維度數值必須比內部箱子中同位置的維度數值還要大。

                EX:  1 . (2,3,4,5) <- (1,2,3,4) -> YES

                        2. (1,3,4,5) <- (1,2,3,4) -> NO

                3、外部箱子維度值的總和必須比內部箱子維度值的總和還要大。

                 EX:  (2,3,4,5) = 14  <- (1,2,3,4) = 10

三、輸入與輸出的規則：

     在輸入時首先有兩個整數在同一行，分別表示箱子的數量及維度接著就是箱子的維度資料，

     另外輸入時必須依照讀取的順序給每個箱子一個編號，在輸出時必須輸出兩行的結果，第一行

     是輸出可形成最大巢狀的箱子數量，第二行則是由內而外依序輸出箱子的編號。輸出的每個數字

     之間間隔一個空白。            PS: 1<= 維度大小<=10 ,    箱子的數量<= 30

     EX:   Sample Input                                      Sample Output

              5 2                                                     5

              3 7                                                     3 1 2 4 5

              8 10                              =>                  4

              5 2                                                     7 2 5 6

              9 11

              21 18

              8 6 5 2 20 1 30 10

              23 15 7 9 11 3

              40 50 34 24 14 4

              9 10 11 12 13 14

              31 4 18 8 27 17

              44 32 13 19 41 19

              1 2 3 4 5 6

              80 37 47 18 21 9

四、演算法的說明：

這個問題主要解法是將資料針對每個箱子的維度進行排序之後再依據每個箱子邊長的總合由小而大

        進行排序；最後再使用遞迴式來計算不同組合的結果，因此如何加快執行的速度關鍵在於如何減少執

        行遞迴的次數：

  4-1、在讀資料時，即可以將每個箱子的維度資料由小到大進行排序並計算其邊長的總合。

        4-2、建立一個指標陣列用來指向每個箱子的記憶體位置並依其邊長總合的大小進行排序。

        4-3、使用遞迴式來依指標陣列的順序來計算不同起始箱子的nesting box數量，但由於已經計算每

                個箱子的長度總合，因此可以先判斷兩個箱子的長度總合是否相差大於等於箱子的維度再進行

                其每個維度值的比較。

        4-4、每次在執行下一層遞迴時先判斷剩餘的箱子是否大於目前已知最多的巢狀收納,如此可以有效的

               減少執行的次數而提高執行速度。

Run time of UVa online web : 0.016

Download : UVa103_StackingBoxes.tar.gz

Result：