3

正如标题所说，从一组整数中找到一个子集，其总和最接近一个值。set里面大概有1000个item，价值1000万左右，我考虑过用DP(Dynamic Programming)来解决这个问题，就像“装箱问题”一样，但是这个方法不适合，set是太大且值太大。

我能做什么，尝试启发式算法？但是如何和使用哪个？

4

2 回答 2

0

I don't know how efficient it would be, but you can try the MILP (Mixed Integer Linear Programming) approach.

LP Formulation:

Variables: Xi = 1 if element No. i is selected.
           Z1: Negative deviation from VALUE
           Z2: Positive deviation from VALUE

Minimize Objective function:
   Z1 + Z2      // Given the nature of problem, at most 1 among Z1 and Z2 shall be > 0.

Subject to constraint:
   summation(WiXi) + Z1 - Z2 = VALUE
   Xi = 0 or 1.
   Z1, Z2 >= 0

You can solve the above Integer Linear Programming using any solver package.

于 2013-09-18T06:09:38.523 回答
0

启发式算法：

订单集从小到大

  1. 查找小于期望值的最大值（二分查找）

  2. 从最小值开始，尝试直到步骤 1 中找到的值。如果完全匹配，您就完成了。否则，直到总和将超过目标。保存此值组合。

  3. 从 1 开始重复。从 1 中找到的下一个较小的值开始，组成另一个总和。重复直到没有值

  4. 筋疲力尽时，选择总和壁橱的目标。

于 2013-09-18T03:30:43.477 回答