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

配列をソートします。最大の項目を取り、最初の項目 (2 番目に大きい項目から開始) を探して、2 つの項目の合計が目標より少なくなるようにします。次に、最小のアイテムから順番に見ていき、一致するかどうかを確認します。そうでない場合は、2 番目の数値を 1 つ下に移動して、もう一度やり直してください。2 番目の値が (最大のもの - ターゲット) の半分未満になるまで、この手順を繰り返します。この時点で、最大のアイテムを破棄し、プロセス全体 (並べ替えを除く) を繰り返します。

ランダム検索よりもはるかに最適な方法でソリューションを見つける必要があります。

于 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 に答える