algorithm - 合計が値に最も近い整数のセットからサブセットを見つける

Question

タイトルが言ったように、合計が値に最も近い整数のセットからサブセットを見つけます。セットには約 1000 個のアイテムがあり、値は約 1000 万個です。この問題を「ビン パッキング問題」と同様に DP (動的プログラミング) を使用して解決することを検討しましたが、この方法は適していません。セットは大きすぎて、値が大きすぎます。

ヒューリスティック アルゴリズムを試してみて、何ができますか? しかし、どのように、どのように使用しますか?

Answer 1

発見的アルゴリズム:

注文セットの最小から最大へ

1. 目的の値よりも小さい最大値を見つける (二分探索)

2. 最小値から始めて、ステップ 1 で見つかった値までの値を試します。完全に一致した場合は完了です。それ以外の場合は、合計が目標を超えるまで。この値の組み合わせを保存します。

3. 1 から繰り返します。1 で見つかった次に小さい値から始めて、別の合計を作成します。値がなくなるまで繰り返す

4. 使い果たされたら、ターゲットに最も近い合計を選択します。