[問題] 類似背包問題

[cutekid (可愛小孩子)]

有 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://www.ptt.cc/bbs/Prob_Solve/M.1418788403.A.5CA.html
→ suhorng: 硬做應該還是可以做到 O(NW1W2W3)?
推 fenzhang: 值是整數還是實數?
→ cutekid: 整數
推 FRAXIS: 你是要最佳解還是近似解？
→ cutekid: 想要最佳解，如果最佳解時間複雜度過高的話，近似解也可
推 FRAXIS: 如果要最佳解 那就試試看DP吧
→ FRAXIS: 不然你可以考慮使用Integer Programming的解法..
→ cutekid: 謝謝大家唷:)
推 aecho: 數學定義都出來了…或許可以考慮Constraint programming
→ aecho: 找到的投影片： http://goo.gl/lzhp2Y
推 aecho: 印象中，GLPK可以用來寫Constraint programming
→ aecho: glpk, http://goo.gl/UYXuM4
→ cutekid: 謝謝 aecho 大大