logo标签列表

给定一组数字和区间的分配算法

algorithmnumbersdistribution
5
我正在寻找一种算法，能够处理以下描述的问题。我已经编写了一个算法（我认为它太专业化了，不能公开），尽可能地优化了它，但在更大的数字集上，它仍然太慢（随着成本的呈指数级增长）。解决方案在一台不错的计算机上应该不超过5秒钟。
你会得到一组数字，例如：
M = {1, 1, 1, 2, 2, 2, 5, 5, 5, 10, 10, 10, 10, 20, 50, 50, 50, ..., 10000, 10000, 20000, 20000}
它们不必具有特殊的结构（尽管它们在这里具有）。
你会得到一组“目标点”，也是数字，例如：
P = {670, 2010, 5600, 10510, 15000}
目标是从 M 中取出最少的数字，当您按照决定的顺序添加它们时，您可以尽可能接近 P 中的所有点。每个数字只能使用一次。
在我们的示例中，可能的解决方案是（虽然我不知道它是否是最佳的）：
Y = (500, 100, 50; 1000, 200, 200; 2000, 1000, 500; 5000; 2000, 2000)
正如您可以看到的，两个标准“最少”和“接近”需要一些权衡。这就是为什么我的当前算法使用评分来找到“最佳”解决方案的原因。
以下是它目前的工作方式：
1.排序 M、排序 P，升序 2.删除数字太小以至于不能显著改变得分或者数字太大的数据 3.递归： 4.将 P 中的下一个点作为当前“目标”，加上或减去例如10％ 5.添加来自 M 的下一个数字，并将其从 M 中删除 6.当靠近目标点时，转到步骤4。如果在结束点，则计算当前分配的得分并可能记忆它 7.否则，转到步骤5 8.从尝试数字返回时，取下一个更高的数字
它从不尝试两个相同的数字，只尝试升序，例如：
  • 100, 100, 100, 50, 50, 20, 10
  • 100, 100, 100, 50, 50, 20, 20
  • 100, 100, 100, 50, 50, 50, 10
  • 100, 100, 100, 50, 50, 50, 20
  • 100, 100, 100, 50, 50, 50, 50
  • 100, 100, 100, 100
  • 100, 100, 100, 100, 10
  • 100, 100, 100, 100, 20
  • ...

如果每个数字有大约5个，并且去掉许多较小的数字，该算法将非常快并找到一个好的解决方案。但是，如果我添加更多数字，特别是包括较小的数字，则运行时间从100ms上升到无限大。

你能给我一些提示如何解决这个问题吗？文献中是否有类似的算法可以处理该问题或其中的一部分？

我应该补充一下，评分是近似的，真正的目标不是找到得分最高的解决方案。但由于当前的评分没有计算有意义的数字（没有与其他分数进行比较），所以最高分是我能想到的唯一方法。也许如果评分没有太大变化，我们可以停止评估当前路径。 - Wikser
3个回答
0

让我试试，可能不是最好的，但应该能很好地工作。我在这里使用PHP -

1）将M中的值及其计数分类：让我们称之为C

$C = array_count_values( $M );

This gives us:
Array
(
    [1] => 3
    [2] => 3
     ...
    [20] => 1
     ...
)

2）从P中取出第一个数字并在M上应用二分查找，得到最接近P1的数字N1（N1 < P1）。从C中减去相应的计数。

    So say you get 500 which is nearest to 670. Now subtract $C[500] - 1.
You can validate if count is not 0 and if zero get the next lower number from M.

3) 获取P1-N1，再进行二分查找以返回最接近的值。将其加到N1上并循环执行，直到获得最接近的总和。

4) 对于P的所有成员，重复执行步骤2和步骤3。

二分查找是关键部分，应该足够高效。

0
它由多个背包问题组成，相互作用： “从区间A中取一个数字放到区间B中是否更好？” 我希望一些额外的约束条件可以降低复杂度。 - Wikser
0
谢谢你的提示。问题的主要部分是“有限”的硬币数量，因为我想不出如何在可能的“更改”上使用动态规划（记忆化），因为它们取决于剩余的硬币（这会产生太多的组合需要记住和比较）:/ - Wikser
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接