0

我正在寻找一个解决方案来总结 3 个数字（在一个数组内 - 这是一个给定的数字列表），它等于一个数字。

例如

$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 个值，这意味着它有很多可能的组合，任何解决方案都可以帮助减少执行时间？

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

4

2 回答 2

1

对数组进行排序。取最大的项目，然后寻找第一个项目（从第二个最大的项目开始），使两个项目加起来小于目标。然后，从最小的项目开始，看看是否有匹配项。如果不是，请将第二个数字向下移动一位，然后重试。重复此步骤，直到第二个小于（最大的一个 - 目标）的一半。此时，丢弃最大的项目，并重复整个过程（减去排序）。

您应该以比随机搜索更优化的方式找到您的解决方案。

于 2012-12-28T03:54:36.737 回答
0

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

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

于 2012-12-28T03:58:24.457 回答