題目連結:
給定一正整數 T (T ≦ 100),代表有 T 筆的測試資料。每筆測資的第一列給定一正整數 N (1 ≦ N ≦ 1000),代表有 N 個箱子。接著的 N 列輸入,每列給定三正整數 W 、 S 、 L (1 ≦ W 、 S 、 L ≦ 10 ^ 9),分別代表一個箱子的重量、最大負重(包含自身的重量)以及長度。
箱子等高、等寬,且可以疊在一起,但要滿足以下條件:
一:長度由上至下非嚴格遞增(也就是放在上面的箱子長度不會超過下面的)
二:任何箱子的上面如果有放其他箱子,則上面的所有箱子之總重(含自己)不超過其最大負重。
試問:最多可以疊幾個箱子?
首先,將箱子們先以長度由小排到大,長度一樣的再以最大負重由小排到大。
接著建立一個一維陣列 DP[i] ,每個 i 值代表「目前」高度為 i 個箱子的塔總重量之最小值。一開始皆初始化為極大的值。代表一開始「目前」的陣列 DP ,沒有任何箱子放入。
因此,我們一個箱子一個箱子地試放看看(以排序後的順序,而且每次都是放在箱子塔的最下面)。可以看到高度為 i 個箱子要放入此箱子時,塔的總重有可能變為從 i - 1 個箱子的塔放入此箱而得,或者是維持上一個的放法,端看哪座最後總重較小。即:
DP[i] = min( DP[i], DP[i - 1] + weight[j] ),其中 weight[j] 代表現在的箱子(編號 j)的重量。
但是在放入之前,要先判斷該塔(DP[i])目前的重量是否超過現在箱子的最大負重。如果超過,也就無法放入(因為箱子要放到最下面),更不用提會去影響現在的塔之重量最小值。
因為 DP[i - 1] 有可能會影響 DP[i] ,因此求目前最佳解的順序應為從大的 i 值到小的 i 值去求。否則,方向錯誤的話會影響解答,因為這樣子會無法判斷這個箱子放入之前和之後的狀態變化。
最後,所有箱子都試著放入後,看陣列 DP 中第一個不是儲存一開始的極大值的位置 i ( i 由大到小看)為何。此時的 i 值即為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。