讀書時學過用DP解
這問題是NP-Complete
先說一說這個問題
有一堆物件,每個有自己的重量及價值
你也有一個負重上限
Input: Goods, each with weight and value AND Weight limit
Output: The set of goods having highest value and under the weight limit
DP solution:
OPT(i) = max value subset of items 1 to i
Case 1: OPT(i) = OPT(i - 1)
This means does not choose item i.
Case 2: OPT(i) = Vi + OPT(i-1)
Add item i to the subset.
Final formula : OPT(i) = MAX ( OPT(i-1) , Vi + OPT(i-1) )
OPT(0) = 0
做法
(像是非必要,但排好的話OPT[]會比較容易理解?)把物品用重量排好(輕至重)
準備一個Array, OPT[道具件數][負重上限]
OPT[n][0] = 0 // 無重量 (n指全部)
OPT[0][n] = 0 // 無物品
開始填滿OPT[][]
OPT[1][n] = V1 (重量許可的話)
V1 = 物品1的價值
解釋: 上限再多物件也只有(最輕的)一件,整行除了上限不足的格數都會是 = V1
OPT[2][n] 就要做加數
比較 OPT[1][n] (上一格) 及 OPT[2][LIMIT - W2] (減去物品重量後左方的格子)
取較高的值,之後記下做 Backtracing
例子在此
物品1 重2 價值3
物品2 重3 價值8
| 物品\重量上限 | 0 | 1 | 2 | 3 | 4 | 5 |
| 0 (沒物品) | 0 | 0 | 0 | 0 | 0 | 0 |
| {1} | 0 | 0 | 3 | 3 | 3 | 3 |
| {1,2} | 0 | 0 | 3 | 8 | 8 | 11 |
解釋
綠色的2格是太重,所以是無物品,價值0
之後的物品{1}都是有價值3
粉紅的8是比較 正上面的3 和 左邊的 0 + 物品2的價值(8) , 發現左邊的比上面的高所以用8, 記住BT要用這個
淺藍的11是比較正上面的3 和 左邊的 3(淺黃格) + 物品2的價值(8), 所以得出 11
左邊格子的選法當然時 重量 - 物品n重量,小於0當0
另一例子
例子在此
物品1 重2 價值3
物品2 重3 價值1
| 物品\重量上限 | 0 | 1 | 2 | 3 | 4 | 5 |
| 0 (沒物品) | 0 | 0 | 0 | 0 | 0 | 0 |
| {1} | 0 | 0 | 3 | 3 | 3 | 3 |
| {1,2} | 0 | 0 | 3 | 3 | 3 | 4 |
這次物品2 價值下降至1
紅色的兩格的選法都是左邊的 0 + 1 和 上面的 3 比,結果還是上面的3比較好
基本上不停的做到最後一格(右下一格)後做 Back-tracing就能找到 OPT(n)
舊問題到此為止
現在的就是改版
靈感是來自大帝國的艦隊編成
大帝國的戰艦有5種價值 及 成本
代表速度的 索敵
4種攻擊的 航空,鐳射,飛彈,魚雷
成本 就是 指揮
輸入 戰艦資料, 指揮上限 及 各價值的希望數值
輸出 是否有滿足的組合(大於或等於希望數值),有的話顯示該組合
忘了一點,大帝國只能選4部戰艦
基本上 0-1 knapsack 可以視為這個大帝國問題的簡單版
因為 0-1 knapsack 只有1種價值
但大帝國的則有5種...
個人想到的注意地方
- 如何在 0-1 knapsack問題上限制只能選4個物品
- 先不想5種價值,先想2種價值(如索敵及鐳射)的做法...相信最後可以推到n種價值也沒問題
- Brute force complexity = O(n!) , n為輸入戰艦數... n! 的原因為 brute force要試 nC4
- 如果用0-1 knapsack的話會有幾個地方出錯 其中一個為如何定義2種價值的OPT,某價值較高某價值較低時如何取捨,用希望數目的百分比也會出錯
- 想過先計出分別2種價值的OPT, OPT[MAX][n]會算出在 COST n 時某單一屬性的最高值及其組合,之後補上雙價值皆非0的戰艦...但如果全部戰艦都是雙價值皆非0就不會做 Orz
