この実際的な問題についてコメントをいただければ幸いです。
簡単な説明。 特定のベルト幅を構成するために使用できる可変数のリンクがあります。問題は、各リンクの数です。選択基準: より長いアイテムを使用することをお勧めします。
例。 ベルト幅 W = 1024.0 を作成したいとします。モデルの 1 つは、次のリンクの長さを持っています: L = [34.0, 65.0, 96.0, 126.0]
問題は、幅を作るために各リンクの数です。
ここに私が試したいくつかのアプローチがあります。
1. 貪欲 (条件を満たすために最長の最初のものを選択) c = [0,0,0,8] ここで、c は各項目のカウントです。これは 16.0 のギャップを残し、最小のアイテムの 1 つでも収まりません。貪欲は簡単ですが、良くありません。
2.選択ループ 簡単すぎず、難しい問題だと思います。私は多くの戦略を試しました。小さなアイテムを詰めてから、次のサイズに合わせて順番に削除します。
3. ナップザック方式 これはアイテム数が決まっているためあまり適切ではありません。
4. 部分和問題 これは Knapsack のサブクラスですが、私はそれを機能させることができませんでした。
5. Bin Packing problem 似ているように聞こえますが、私の問題には当てはまりませんでした。
6. ブルート フォース (ランダム選択) 奇妙なことに、これは多くの正確な一致を見つけます。カウントの単純な多項式を評価として使用します。rating = n[0] + n[1]* 2 + n[2] *3 + n[4]**4 + ... ブルート フォースからの解の 1 つは [4, 0, 4, 4] です。正確には 1024 です。問題は、この方法では異なる選択が行われることが多いため、理想的ではないことです。
7. 網羅的検索 選択肢が多すぎるため実用的ではありません。
8. シミュレーテッド アニーリング ブルート フォースの成功からすると、これは良い代替手段のように見えます。誰かが簡単な例を教えてくれませんか (別の巡回セールスマンはやめてください)。
9. 遺伝子群と粒子群 これらについては不明です。
今、私は立ち往生してイライラしています。この問題に使用できる直接アルゴリズムはありますか?