java - ビンパッキング総当たり法

Question

ビンパッキング問題を解くプログラムを作る必要があるのですが、最初に当てはめて貪欲なアルゴリズムを作ったのですが、講師が問題の最小解を見つけられない場合があると言っています。だから私はブルートフォースを試すことにしましたが、考えられるすべての解決策をどのようにチェックするべきかわかりません。そうそう..誰かが私に説明したり、疑似コードなどを提供したりできますか。大変感謝しています。

Answer 1

ブルートフォースはすべての組み合わせを試すだけです。

ブルート フォースのコードを作成するには、次のトリックを検討してください。8 つのネストされたループをハードコーディングせずに、8 つのクイーンのすべての組み合わせにアクセスしたいとします。次の 8 つのゼロからなる 8 進数を考えてみてください。

00000000

次に、8 進数システムでそれを増加させる単一のループを記述します。

00000001
00000002
00000003
...
00000007 // 7 + 1 = 10
00000010
00000011
00000012
...
77777776
77777777

これにより、8 つの内部ループをハードコーディングすることなく、すべての組み合わせが試行されます。8 を n に置き換えても、同じコードが機能します。

Answer 2

明らかに力ずくよりもうまくやれる。まず、ビンの最小数を計算します。サイズが 100 のビンと合計サイズが 1,234 のアイテムがある場合、12 個のビンには収まりませんが、13 個には収まる可能性があります。

ビンが 13 の場合、未使用のスペースは 66 (1,300 - 1,234) になります。5 x 13 = 65 なので、サイズが 6 の未使用のビンが少なくとも 1 つ必要です。ですので、6号以下のサイズのものがあれば、最終的にはなんとか収まるので計算から外していただいても構いません（もちろん実数で確認する必要はありますが、とにかく小さいものは検索から除外されます）。

2 つのアイテムがビンを正確に満たす場合、それらが適合しないソリューションを考慮する必要はありません。

それ以降は動的計画法を使用しますが、常に最大の未使用アイテムを新しいビンの最初のアイテムとして使用すること、常にビンにアイテムを降順で入力すること、アイテムがなくなるまで常にアイテムを追加すること、組み合わせを考慮しないことを除きます。すべてのアイテムが別の組み合わせよりも小さいか、同じサイズです。そして最後に、必要なビンの最小数と同じくらい良い組み合わせが見つかったとき、最適なソリューションが見つかりました。