PHP Sum 3数字等于精确数字(性能问题)

Question

我正在寻找一个解决方案，求和3个数字(在一个数组内-这是一个给定的数字列表)，这是一个精确的数字。

e.g

$sum = 172300
$array = array(11000,
1100,
2000,
1000,
4500,
83200,
3700,
29000
7000,
500,
1000,
2000,
20000
)

我已经尝试过这个解决方案，但是，我将PHP设置为execute_time到6000也不能给我一个结果。https://stackoverflow.com/revisions/76ee7de8-574f-4b0a-b078-8edff66d885d/view-source

我希望我能得到帮助来解决这个问题。我试过3SUM解决方案，也不能输出结果。

我的数组列表得到了大约100个值，这意味着它是许多可能的组合，任何解决方案都可以帮助减少执行时间？

我需要帮助来解决这个问题..

Answer 1

我相信你正在寻找这个算法http://en.wikipedia.org/wiki/Knapsack_problem

更准确地说，http://en.wikipedia.org/wiki/Subset_sum_problem

Answer 2

对数组进行排序。选择最大的项目，然后查找第一个项目(从第二个项目开始)，这样两个项目的总和就会小于目标。然后，从最小的项目开始，看看是否有匹配。如果没有，请将第二个数字下移一，然后重试。重复这一步，直到第二个小于一半(最大的一个目标)。此时，丢弃最大的项，并重复整个过程(减去排序)。

你应该以一种比随机搜索更优的方式找到你的解决方案。