2

问题

假设我们有一组N个实数 A = {x_1, x_2, ..., x_N}。

目标是将此集合划分为A_1、A_2、...、A_L子集，并限制sum( A_i ) <= T并最小化此项：

成本 := sum( abs( sum(A_i) - T ) )

其中sum(A_i)表示 A_i 中数字的总和，T是给定的阈值。

我正在寻找一种非进化最优算法。

更新： x_i是实数并且不大于T ( 0 < x_i <= T )。

更新 2：固定成本函数。

不错的尝试，贪心算法！

一个简单的想法是使用贪婪方法来解决问题。这是一个伪代码：

 1. create subset A_1 and set i=1.
 2. remove the largest number x from A.
 3. If sum(A_i) + x <= T
  * put x into A_i
 4. Else
  * create a new subset A_i+1, 
  * put x into A_i+1 
  * set i=i+1
 5. If A is non-empty
  * goto step 2.
 6. Else
  * return all created A_i s

问题是这个解决方案不是最优的。例如，在某些情况下，最好不要将两个最大的数x1和x2放在第一个子集A_1中，即使它们不超过T，因为没有其他 *x_i* 可用于添加到该集合并使它的总和更接近T。另一方面，如果我们将x1和x2放在不同的集合中，则可以找到更好的解决方案（成本值较小的解决方案）。

可能的解决方案

我曾想过使用回溯算法，它也可以找到最佳解决方案，但我猜它在这个问题中的复杂性会很高。

我已经阅读了维基百科上的一些文章，例如装箱问题（NP-hard [sighs...]）和切割库存问题，显然我的问题与这个标准问题非常相似，但我不确定哪一个符合我的情况。

4

1 回答 1

2

更新： 使用校正后的成本函数，请注意 sum(A_i) - T 将始终为负，因为 A_i <= T。所以我们的目标是最小化

总和（abs（总和（A_i）-T））=总和（T-总和（A_i））= L*T-总和（A）

sum(A) 是常数，因此任务是最小化使用的 bin 数量。因此，您的问题相当于经典的装箱问题。

为了解决这个问题，您可以使用像这样的装箱求解器。

于 2012-06-02T13:19:59.280 回答