作者cutekid (可愛小孩子)
看板Prob_Solve
標題[問題] 類似背包問題
時間Wed Dec 17 11:53:20 2014
有 n 個 items(維度 3):
(X1,Y1,Z1) = V1
(X2,Y2,Z2) = V2
...
(Xn,Yn,Zn) = Vn
有一個背包(維度 3):
(W1,W2,W3)
現在要從 n 個 items 選出 m 個(不能重複選)使得:
x1 + x2 + ... xm = W1
y1 + y2 + ... ym = W2
z1 + z2 + ... zm = W3
且
v1 + v2 + ... vm 的值最大
請問這樣的問題有什麼好的解法嗎？
謝謝大家 ^_^
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.221.80.36
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1418788403.A.5CA.html
1F：→ suhorng: 硬做應該還是可以做到 O(NW1W2W3)? 12/17 16:32
2F：推 fenzhang: 值是整數還是實數? 12/17 16:52
3F：→ cutekid: 整數 12/18 11:05
4F：推 FRAXIS: 你是要最佳解還是近似解？ 12/18 22:25
5F：→ cutekid: 想要最佳解，如果最佳解時間複雜度過高的話，近似解也可 12/19 10:33
6F：推 FRAXIS: 如果要最佳解 那就試試看DP吧 12/19 21:19
7F：→ FRAXIS: 不然你可以考慮使用Integer Programming的解法.. 12/19 21:19
8F：→ cutekid: 謝謝大家唷:) 12/26 12:21
9F：推 aecho: 數學定義都出來了…或許可以考慮Constraint programming 12/29 14:12
11F：推 aecho: 印象中，GLPK可以用來寫Constraint programming 12/29 14:16
13F：→ cutekid: 謝謝 aecho 大大 12/29 14:44