問題タブ [bin-packing]

質問は言う、

サイズ n の配列が与えられた場合、配列を出力/分割して、合計が N になるサブセットにする必要があります。

URL Dynamic Programming3で同様の問題/説明を見ました

そして、私はpdfに次のクエリを持っています:-

1. 論理はサブセットが存在するかどうかしか分からないので、合計が N になるサブセットをどのように見つけることができるでしょうか?
2. また、質問を少し変えると、同じイデオロギーを使用して平均が等しい 2 つの部分集合を見つけることができますか?

誰でもこの動的プログラミングの問題に光を当てることができます.. :)

前もって感謝します..

フォントグリフ画像を単一のテクスチャにパックしようとしています。ビットマップは1ピクセルあたり1バイトの単色であり、すべてを1つのテクスチャにまとめたいと思います。必要な最小テクスチャサイズを計算することはできますが、それらをすべてまとめるアルゴリズムを管理することはできません。

現在、ビットマップをcharポインターとして保存しており、それぞれのサイズを取得できます。

PHPを使用して1つの大きな正方形/長方形にまとめたい、さまざまなサイズの正方形と長方形のコレクションがあります。四角形は通常、モンタージュにしたいイメージですが、単に数学オブジェクトである場合もあります。

これにはPHPアルゴリズムがあり、このタイプのものは何と呼ばれていますか?

更新：さらに検索した後、私が欲しいのはビンパッキング問題と呼ばれると思います。ただし、人間の関心を可能にするために、特定の種類のパッキングの問題 (画像など) に対してある程度のランダム化も追加したいと考えています。

ここで述べたものと同様の矩形パッキング クラスを実装しました。私の最終的な目標は、多数の小さなスプライトを大きなスプライトシートに詰め込むことです。

私が経験している困難は、そのアルゴリズムを拡張して静的な長方形を可能にする方法を考え出すことです。つまり、梱包プロセス中に位置が静的なままであり、回避する必要がある障害物として効果的に扱われる四角形です。

私が検討すべき別のアルゴリズム、またはおそらくこれを行うためのより効率的な方法はありますか?

最も効率的な方法で問題を解決するアルゴリズムを探しています。

問題の説明:

アイテムのリスト（正の整数のみが許可されています）と、同じ容量の固定数のビンがあります。これまで分枝限定アルゴリズムについて考えてきましたが、この場合、それが最善のアプローチであるかどうかはよくわかりません。

例：

アイテムのリストが与えられた場合:

そして、それぞれ9個の容量の3つのビンを詰める必要がありますこれ: (アイテムの順序は関係ありません)

これはビンパッキング問題 (NP 完全であることはわかっています) の変種だと思いますが、使用するビンの数を最小化しようとしていないので、より良い解決策があるのではないかと思います。

私は時間の最高の組み合わせを選択するSQLクエリを持っています。

ただし、反復するために行数が増えると、問題があります。非常に時間がかかります。注:- 上記の行のコメントを外して、問題を確認してください

これに関するヘルプは大歓迎です

この実際的な問題についてコメントをいただければ幸いです。

簡単な説明。 特定のベルト幅を構成するために使用できる可変数のリンクがあります。問題は、各リンクの数です。選択基準: より長いアイテムを使用することをお勧めします。

例。 ベルト幅 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. 遺伝子群と粒子群 これらについては不明です。

今、私は立ち往生してイライラしています。この問題に使用できる直接アルゴリズムはありますか?

オーバーラップを最小限に抑えながら、異なるサイズの長方形をより大きな長方形内に分散させるのに役立つアルゴリズムを探しています。

ビン パッキング アルゴリズムを見てきましたが、長方形の間のスペースの量を最小限に抑えるようです (私の場合、パックされるすべてのアイテムは正方形になります)。

すべての正方形と外側の長方形の境界線との間の距離を最大にしたいと思います。

これが私がやろうとしていることの例です:

特定の条件に基づいてビンパッキングを行うアルゴリズムがあります。読者が理解するには、アルゴリズムのフローが少し複雑であることがわかりました。

以下に、開発されたJavaコードを示します。このコードのはるかに単純化された代替フローはありますか？

ノート：

ptim->現在の時刻

etim->終了時間

lim->制限

スタックオーバーフローについても同様の質問がいくつかありますが、NP困難な問題やアルゴリズムをしっかりと理解していない人が理解できる具体的な答えはありません。

長方形のオブジェクトの2Dビンパッキングをどのように実行しますか？私の場合、最小のスペースを使用して、スプライトシートとして使用するために、複数の画像を1つの画像にまとめようとしています。各画像には大きく異なる境界がある可能性がありますが、コンテナに設定された境界はありません。

私は、ビンパッキングアルゴリズムを理解している誰かが、ビンパッキング方法の一般的な概要を提供するのではなく、これをプログラムで実現する方法を説明できることを望んでいました。