有 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 的值最大
請問這樣的問題有什麼好的解法嗎？
謝謝大家 ^_^

硬做應該還是可以做到 O(NW1W2W3)?

值是整數還是實數?

整數

你是要最佳解還是近似解？

想要最佳解，如果最佳解時間複雜度過高的話，近似解也可

如果要最佳解 那就試試看DP吧不然你可以考慮使用Integer Programming的解法..

謝謝大家唷:)

數學定義都出來了…或許可以考慮Constraint programming找到的投影片： http://goo.gl/lzhp2Y印象中，GLPK可以用來寫Constraint programmingglpk, http://goo.gl/UYXuM4

謝謝 aecho 大大