c# - 最適な組み合わせを決定するアルゴリズム - ビン パッキング

Question

それぞれが値を持つアイテムのセットを指定して、コレクションに含める各アイテムの数を決定し、合計値が指定された制限以下になり、合計値ができるだけ大きくなるようにします。

例：

製品A = 4
製品B = 3
製品 C = 2
製品 D = 5

Total Capacity = 10.5 の場合、B、C、D の組み合わせが選択されます。
Total Capacity = 12.5 の場合、A、B、D の組み合わせが選択されます。
Total Capacity = 17 の場合、A、B、C、D の組み合わせが選択されます。

組み合わせを決定するアルゴリズム (ナップザックやビン パッキングなど) を探しています。どんな助けでも感謝します。

Answer 1

これは「ナップサックのようなもの」だとおっしゃっています。私が見る限り、これは0-1 ナップザック問題と呼ばれる有界ナップザック問題の特殊なケースです。

NP完全です。

それを解決しようとする方法はたくさんあります。1 つのアプローチについては、この関連する質問を参照してください。

• C# で 0-1 ナップザックのシミュレーテッド アニーリング アルゴリズムを作成する

アイテムが 4 つしかない場合は、すべての可能性をテストするだけで、ほとんどの目的に十分な速度であるはずです。