有 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 大大