算法优化组值列表

我有几个数字。我需要将它们分成几组，以便一组中所有数字的总和在预定义的最小值和最大值之间。关键是要尽可能少地将数字分开。算法优化组值列表

Input: 
    min, max: range for sum of numbers 
    N1, N2, N3 ... Ni: numbers to group 
Output: 
    [N1,N3,N5],[Ni,Nj,Nk,Nm...]...: groups where sum of numbers is between min and max 
    Na,Nb,Nc...: numbers, left ingrouped.

来源

2011-07-25 F0RR

这不是问题;这是一个工作描述。你有什么尝试？什么没有用？ –

只是要清楚：很少的数字未分组，或未分组数的最小累计值？你宁愿留下一个3？或两个1？ –

如果你不担心效率，简单地生成每一个可能的分组，并选择一个是在你所描述的感觉正确的和最佳的。显然，这适用于任何有限的数字列表（根据定义，它是最优的）。

如果需要提高效率，问题似乎变得更加困难。：D我会继续思考。

编辑：来想一想，这个问题似乎至少与“子集总和”一样难，因此，我不认为有一个解决方案明显比我给予的解决方案更好（即，没有已知的多项式时间算法可以解决这个问题，如果它是NP-Hard

来源

2011-07-25 13:59:18 Patrick87

这个问题可以看作是垃圾箱的大小为max，有一个有趣的目标：最小化没有包装进垃圾箱的项目的数量min。装箱文献中的一个想法是，“小”物品（在这种情况下，相对于max - min较小的物品）很容易打包，但对大部分组合爆炸的可能性负责，因此一些近似算法为了装箱做一些事情聪明的大项目，然后填写小。另一种减少可能性的方法是将数字四舍五入成为一个较小的集合。如何做到这一点对于垃圾箱来说是非常明显的（整理），但不清楚该如何解决这个问题。

好的，我将举例说明这些想法如何实例化。假设max = 1，min = 1/2。让我们尝试找到一个解决方案，当max = 2和min = 1/2时，这个解决方案与最佳值相竞争。（这可能听起来很糟糕，但这种近似保证OPT在更高的标准下有时会被用于文献中。）

首先将每个项目的大小设置为2的幂。非常大的项目，大小为4或更高，不能打包。大型物品，大小为2或1或1/2，都有自己的垃圾箱。尺寸为1/4或更小的小件物品的处理如下。只要两个尺寸等于或小于1/4的项目具有相同的尺寸，将它们合并为一个超级项目。将所有尺寸为1/2的新物品装入自己的箱子中。其余的总尺寸小于1/2。如果另一个垃圾箱中有空间，请将它们放在那里。否则，给他们自己的垃圾箱。

对于max = 2，所得解决方案的质量至少与OPT的max = 1的质量一样好。对于max = 1并围绕项目大小采取最佳解决方案。坏箱的设置保持不变，因为没有物品更小，并且每个箱子的存储量小于2，因为每个物品的尺寸小于以前的尺寸的两倍。现在，足以证明我给出的2的幂的包装算法是最优的。我将把它作为一个练习。

我不认为这会立刻推广到一个完整的算法。我必须回去工作，但我会采取的做法是强制OPT处理最大值= 1，而ALG获得使用max = 1 + epsilon，替代（1 + epsilon）的幂数四舍五入的步骤，然后找出如何打包小项目，可能使用动态程序，因为贪婪可能无法工作。

来源

2011-07-25 15:04:35 insomniac

+1（我赞成这个），但你可以发展多一点？ –

@Ricky Bobby我希望你找到我的编辑有用。通过阅读我的答案，我想主要想法是通过比较算法与更受限制的最佳值来测量近似最优性。我希望F0RR的用例可以。 – insomniac

thx我很高兴看看它 –

算法优化组值列表

回答

相关问题