作者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/cn.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