問題タブ [bin-packing]

これが私の問題です：

• 商品を販売している会社はn社あります。
• すべての製品は k 日以内に配布する必要があります
• Ci 社の製品は連続して配布する必要があります。つまり、2、3、4、5 日には配布できますが、2、3、6、7 日には配布できません。
• 企業 Ci が j 日に配布した製品の数は、j-1 日よりも少ない (または等しい) 必要があります (j-1 日にあった場合)。
• i 日目と j 日目の配布された製品の差は 1 を超えてはなりません

例：

商品発送まであと3日です。A社の製品：a、a、a、a、a。B社の製品：b、b、b。C社の製品：c,c

公平な配布: [aab,aabc,abc]

無効な分布: [aabc,aabc,ab] 1 日目には 4 つの製品があり、3 日目には 2 つの製品があるため (差 > 1)

無効な分布: [abc,aabc,aab] 1 日目には 1 つの製品 A があり、2 日目には 2 つの製品 A があるため、製品 A の分布は非減少ではありません

EDIT 公平な配布が不可能な場合は、簡単な説明を付けてください。回答を受け付けます

私の質問に対する「完璧な」解決策はおそらくないことを私は知っています（これはナップザックのバリエーションまたはビンパッキング問題のように聞こえます）が、これが私のシナリオです：

SQLデータベーステーブルのリストをn個（たとえば7個）のほぼ同じサイズのパイルに分割したいと思います（これにより、一部のメンテナンスタスクを1週間全体にほぼ均等に分散できます）。

サイズ1からサイズ10,000,000までの範囲の100個のテーブル（これは高くても低くてもかまいませんが、5000より高くなることはないでしょう）があるとしましょう（もちろん、大きなテーブルはそれほど一般的ではありません）。

私の当初のアイデアは、テーブルをアルファベット順に（疑似ランダムに）並べ替えてから、最初からウォークスルーし、合計がSum（Size）/7を超えると次のグループに移動することでした。一部のデータベースでは、これはおそらく正常に機能しますが、2つの巨大なテーブルが隣り合っている場合、これは非常に不均等なグループになります。（これは思ったほどありそうもないことではありません。Account_HistoryとAccount_History_Archiveの2つの巨大なテーブルを検討してください）。

さまざまなソースデータで「良好な」結果をもたらす、一般的に受け入れられている手法はありますか？私は、より正確なグループ化ではなく、より単純な手法に傾倒します（メンテナンスが他の日よりもわずかに長く実行される場合、それほど大きな問題ではありません）。

多分誰かが石（異なる重量）を異なるサイズのバックパックに入れるためのアルゴリズム、またはそれがどんな名前を持っているか知っていますか？私はPrologでそれをするべきです。石の重さとバックパックの容量を示します。プログラムは私にこれらすべての石をバックパックに入れる方法を教えてくれるはずです。

私がやりたいのは、画像（私の場合は2048x2048）を作成することです。アルゴリズムは次のように機能するはずです。

-ユーザーがフォルダからいくつかの画像を選択し、プログラムに「画像を生成」と指示します

-プログラムは、すべての画像を1つの画像内に収めることができるかどうかをチェックします（サイズの問題）。そうでない場合は、エラーメッセージを返します。

-プログラムは、すべての画像を画像内に配置する正しい方法を見つけてから、ユーザーに保存パスを選択するように促します（明らかに古い画像はサイズ変更/切り取りしないでください）

問題は明らかに最後のステップです。実際にそれを行う方法がわかりません。また、画像のファイル名がmyimage_1であり、「myimage_2」がある場合、プログラムがチェックする必要がある別のこともあります。これらの画像は互いに近くに配置する必要があります。 （3、4などもほぼ同じ）

誰かがこれを手伝ってくれますか？

私のタイトルが理にかなっていることを願っていますが、これが私がやろうとしていることです:

それぞれnの幅が W _nで高さが H _nの四角形があり、2 次元 (x,y) 平面上でそれらがすべて収まる四角形が最小面積を占めるように配置する必要があります。また、どの (x,y) がどの四角形に対応するかを確立できる必要もあります。

私は疑似コードで何かを好むだろうが、多くの言語で動作する.

助けてくれてありがとう。

サイズの異なるオブジェクトのバンドルがあります（多くのオブジェクトが同じサイズになる可能性があります。たとえば、6Bのオブジェクトが54個、10Bのオブジェクトが76個、24Bのオブジェクトが79個などです。

オブジェクトのサイズは6、8、10 ....バイトです）。そのバンドルをカップルメッセージにパックする必要があります（各メッセージの最大長は256バイトです）。

問題は、最小数のメッセージで解決策を得る方法ですか？

このための既知のアルゴリズムはありますか？これにはホップフィールドニューラルネットワークが必要ですか？

無限の容量のn 個のビンが与えられた場合、最も重いビンの重量を最小限に抑えながら、m個のアイテム (それぞれが特定の重量を持つ)にパックしたいと考えています。

これは、ビンの容量が有限であり、使用するビンの量を最小限に抑えようとする従来のビン パッキング/ナップザックの問題ではありません。一定量のビンがあり、それらをすべて使用して、最も重いビンの重量をできるだけ低くしたいと考えています。

この問題に名前はありますか？キーワードを含む多くの論文に目を通しましたが、似たようなものは見つかりませんでした.

乾杯。

アイテムのセット（1〜100のサイズ）とビンの数（1〜15）が与えられた場合、ビンのサブセットを持つ各アイテムには、アイテムを割り当てることができ、どのビンが最適、2番目に最適、など、それだけです。アイテムには自然な順序もあります。たとえば、item1の前にitem2の名前を付けることで、以下に示します。各ビンの容量は1〜5です（すべてのアイテムの重量は同じ、つまり1です）。

入力の例としては、3つのビンと6つのアイテムがあります（-は、ビンがアイテムの使用可能なセットにない、つまり、ビンをパックできないことを示します）。

目標は次のとおりです（競合が発生した場合に、各目標が下位の目標を完全にオーバーライドするために、たとえば、使用されるビンの数や設定が無視される場合でも、5つのアイテムをパックする方が常に4つよりも優れています）。

1. 梱包されたアイテムの数を最大化する
2. アイテムを自然な順序でパックします。たとえば、ビンの合計容量が1で、アイテムが2つある場合、item1はパックされ、item2はパックされません。
3. 使用するビンの数を最小限に抑える
4. ビンの設定と自然な順序に従って各アイテムをパックします。つまり、最初の設定のitem1と2番目のitem2は、2番目のitem1と最初のitem2よりも優れています。
5. 2つのソリューションがこれらの目標によって区別できない場合、たとえば、実装の副作用または単なる任意のタイブレークとして、どちらのソリューションも上位にランク付けすることができます。

したがって、上記の入力は次のようにパックされます。

問題は、最初の段落からの入力サイズと数秒の時間制約、つまりブルートフォース（または少なくともブルート）ではなく、この問題を解決するためのアルゴリズムのアイデアを思い付くのに役立つ、何を読んでレビューするかです。これまでに考えた力です。）私はRubyとCを使用していますが、森のつまずきのこの段階では、言語はあまり関連性がありません。

読書の提案、アルゴリズムの組み合わせに関するアイデア、または問題の説明を明確にするための考えに感謝します...

アップデート1

不明確ではありませんが、これのさまざまな部分をカバーする多くのアルゴリズムがありますが、私の難しさは、すべての基準を一緒に処理する情報を見つける（またはおそらく認識する）ことです。 -ビンセットとアイテム設定。これは、次の例でより明確に示されることを願っています。

bin1が最も優先されますが、item3はまったく配置できません。また、bin2はすべてのアイテムで次に優先されますが、3つのアイテムのうち2つしか保持できません。したがって、割り当ての正しいセット（x）は、実際には最も優先度の低いビンです。

更新2 目標がどのように関連しているかに関する情報を使用して説明を作り直し、ビンの優先度の変数を削除しました。これは、回答を見つける可能性が低くなり、作業中のシステムの他の場所で回避できるためです。

私は Tetris タイプの HTML5 ゲームに取り組んでおり、スペース最適化アルゴリズムを強化する必要があります。さまざまなサイズの長方形ブロックは、最もスペース効率のよい方法でキャンバスに追加する必要があります。ブロックがどれだけのスペースを占めるかはわかっています。ブロックを追加できる最も近いスポットを固定の x 座標で見つける必要があります。絶対的に最も近いスポットがあると便利です。

キャンバス上でピクセルごとの値チェックを使用して検索し、形状に十分な空き領域が見つかるまで押し下げてから追加するバージョンを実装しました。これは、スペースが左から右に塗りつぶされている場合にのみ（ゆっくりと）機能します。アルゴリズムは、最初のピクセル列が安全である場合、ブロック全体を追加できると安全に想定できます。

これをより堅牢にする必要があります。これが私が考えるところです。

ボードの状態を表すクワッド ツリーを格納すると、どこにスペースがあるかをすばやく特定できます。

深さのレベルごとに 4 つのノードが格納されます。各ノードは、完全に空の場合は 0 で、「どこかに何かがある」場合は 1 です。深さの段階ごとに、ボードに関するより多くの情報が得られます。

グリッドを表現するのに最適な JavaScript データ構造は何ですか?

これまでに検討したこと：

A.tree子と値へのポインターと、それをナビゲートするための一連のメソッドを含む完全なオブジェクトを作成します。これは直感的で、おそらくスペース効率が良いでしょうが、恐ろしく遅いと思います。

B. 各グリッドを 4 ビットとして見て、深さを 16 進配列またはオブジェクトとして格納します。私よりも賢い人がこれを行うと、おそらくストレージが最適化されるだけでなく、隣接するセルを比較したり、ブロックをオンまたはオフにしたりするための巧妙なビット操作が可能になります。構築する私のスキル。

C. 各深さを配列に格納します。 Depth[0]=[1,0,0,0]; Depth[1][1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0]等 これは私が今向かっているところです。スペース効率はあまり高くなく、おそらく信じられないほど高速ではないでしょうが、理解できると思います。

深さの数に対する構造には実質的な制限があります (私の最後のアプローチで 4x4 スペースの可用性を格納するための配列は 65,000 を超えます)。その後、キャンバスから画像データの最後の数ピクセルをチェックするための高価な呼び出しを行います通常の反復子は避けられません。

それで、A、B、C、その他？

いつものように、すべての洞察に感謝します。

私は以前、木材、ガラス、石などで物を製造するためのソフトウェアに取り組んでおり、部品を自動的にレイアウトして無駄を最小限に抑える手段を提供していました。あなたの多くは、これをビンパッキング問題として知っています。私はこれに出くわしました - http://www.dropbox.com/jobs/challenges#packing-your-dropbox - そして興味深い問題を見つけました。

通常、ディスク領域は 1 次元配列と見なされ、ファイルは互いに収まるように分割されます。ただし、ここでは、それらは重なっていない長方形です。私はアプリDisk Inventory Xを使用しています。これは、ファイルシステムの視覚化に同じ概念を使用しています。

私の無知とGoogleクエリを適切に構築できないことを許してください。誰かが私に説明してもらえますか?これは実際の実装とどのように関係していますか?

これがファイルがディスク上に配置される方法であると仮定すると、入力データと消費される時間/メモリの実際の要件は何ですか?

どうもありがとう！