-1

数値のリストを同じサイズの2つの「ビン」に分割するために、First-Fit-Decreasingビンパッキングアルゴリズムを実装しました。アルゴリズムはほとんどの場合、最適なパッキング配置を見つけますが、そうでない場合もあります。

例えば：

数字のセット4、3、2、4、3、2は、明らかにこの配置に分割できます：1）4、3、2 2）4、3、2

最初の適合減少アルゴリズムは解決策を見つけられません。

この状況では、正しい解決策が存在する場合にそれを見つけられないことは受け入れられません。

元のパズルは、数列を等しい合計を持つ2つのセットに分割することです。

これは単なるビンパッキング問題ですか、それとも間違ったアルゴリズムを使用しましたか？

4

1 に答える 1

2

ビンパッキングはNP完全です。

この状況では、正しい解決策が存在する場合にそれを見つけられないことは受け入れられません。

分枝限定アルゴリズムを試してみてください。ただし、すべての正確なアルゴリズムと同様に、中規模または大規模の問題には対応していません。

First-Fit-Decreasingは、決定論的アルゴリズムを開始するのに適していますが、シミュレーテッドアニーリング、タブーサーチ、遺伝的アルゴリズムなどのメタヒューリスティックとチェーンすることで、はるかに優れた結果を得ることができます。Drools Planner（java）など、それを実行できるオープンソースライブラリがいくつかあります。

于 2011-02-15T10:19:30.233 に答える