問題タブ [bin-packing]

要素間の空白を最小限に抑える方法で、要素で埋められるレイアウトを作成しようとしています。問題は、私が試したすべてのライブラリが、定義された方法で左から右、上から下にアイテムを並べ替えることです。次に例を示します。

このアイテムは、layout_wrapper を左から右、上から下に 1 から始まり 4 で埋めます。しかし、この方法では、他の適切なアイテムで埋めなければならないギャップが生じる可能性があります。たとえば、1、4、3、2 としましょう。レイアウトを埋める最適な方法。

しかし、私はこれを機能させることができません。これは、動的なコンテンツの読み込みなど、コンテンツを適切な方法で配置する必要がある状況では一握りであることはわかっていますが、私の場合は別の動作が必要です。

それで、masonry.jsまたは他の同様のライブラリでこれを機能させて、ビンパッキングアルゴリズムを必要な方法で機能させる方法を知っている人はいますか? ありがとう。

1D ビン パッキング問題の解決に取り組んでおり、初期集団として、MBS のジェネレーター パーティクルから始めます。MBS' (最小ビン スラック) アルゴリズムをネットで探していましたが、見つかりませんでした。誰か助けてください。

ビンのパッキングについての私の理解では、事前に決定された、多くの場合異なるサイズのオブジェクトを、事前に決定された固定サイズの 1 つまたは複数のコンテナーまたは「ビン」に収めようとしています。固定サイズの単一のコンテナーと、それに収まる必要がある固定数の要素があるという問題があります。違いは、私の要素は固定サイズではなく、特定の任意の倍数にサイズ変更できることです。番号。例えば：

280x420 のコンテナーに完全に収まる必要がある 3 つのオブジェクトまたは要素があり、オブジェクトのサイズを 140 の倍数に変更する必要があるとします。

したがって、次のように収まる可能性があります: (または垂直方向に反転)

または: (または水平方向に反転)

最終的に、各ボックスのサイズは統計に基づいて動的に決定されます。(たとえば、1 つの項目の統計値が 90% で、他の 2 つの項目の統計値が 2% と 8% の場合、明らかに 90% の方が大きなボックスになります。) ただし、複雑になりすぎないようにしています。それはまだなので、コンテナを満たすアルゴリズムを作成することが私の主な目標です。

私はさまざまなアルゴリズムを研究してきましたが、これを試みる理想的な方法をまだ考え出していません。ポインタはありますか？例？類似の既存の数学的アルゴリズムまたはその他のアルゴリズムはありますか?

より複雑な例: 6 個のアイテム、560x420 のコンテナ。要素の JSON: { "0": "432", "1": "389", "2": "403", "3": "190", "4": "215", "5": "832" } 可能なレンダリングの 1 つ:

回転せずに四角形をパッキングするアルゴリズムはありますか?

おそらくC++での実装ですか？

私はこれを見つけました

と

• ギロチンビンパック
• シェルフビンパック
• SkylineBinPack

しかし、それらは長方形を回転させます。

可変サイズのボックスが 3 つあります。

サイズの商品がありますa: 1, b: 2, c: 2, d: 3, e: 5

私は明らかにそれらを次のパターンに適合させることができました：

しかし、次のようにすることもできます。

このようなすべての可能なパッキングを取得する方法はありますか?

これはビンパッキングの課題のように感じますが、「最適な」解決策を見つけようとしているのではなく、すべての (または少なくとも複数の) 可能な解決策を見つけようとしています。

ソリューションがヒットするまで、アイテムに対して単純なビンパッキングアルゴリズムをランダムな順序で実行できると思いますが、それは本当に非効率的です...

何か案は？

奇妙なビンパッキングの問題を解決しようとしています。元の問題へのリンクはこちらです (長い質問で申し訳ありません。ご理解いただきありがとうございます)。

私は次のように問題を繰り返しています: 区画化された Panel の描画を生成するアプリケーションを作成しようとしています。

N 個のキュービクル (2D 長方形) があります (N <= 40)。各キュービクルには、最小の高さ (minHeight[i]) と最小の幅 (minWidth[i]) が関連付けられています。パネル自体にも MAXIMUM_HEIGHT 制約があります。

これらの N 個のキュービクルは、各キュービクルで上記の制約が満たされるように、列方向のグリッドで上下に積み重ねる必要があります。

また、各列の幅は、その列の各キュービクルの最大 minWidths によって決まります。

また、各列の高さは同じでなければなりません。これにより、パネルの高さが決まります

任意の列に残っている空きスペースに予備のキュービクルを追加したり、指定された最小値を超えて任意のキュービクルの高さ/幅を増やすことができます. ただし、キュービクルを回転させることはできません。

パネルの MAXIMUM_HEIGHT = 2100mm、最小幅範囲 (350mm から 800mm)、最小高さ範囲 (225mm から 2100mm)

選択した答えに従って、整数線形計画法を定式化しました。ただし、問題の組み合わせの性質を考えると、ソルバーは N > 20 で「ハング」しているように見えます。

現在、回避策を実装しようとしています。

キュービクルは、minWidths の降順で並べ替えられます。minWidths が等しい場合は、minHeights の降順で並べ替えられます。次に、 First Fit 減少ヒューリスティック
を使用して解決します。これにより、合計パネル幅の上限と、現在の列幅のリストが得られます。

今、私はパネルの幅を小さくして、フィーダーをその小さいサイズのパネルに合わせようとしています. （フィーダーが特定の列幅のリストに効率的に収まるかどうかを確認できます）

パネルの幅は、次の方法で小さくすることができます:
1. 任意の列を取り、次に低い minWidth フィーダーの列に置き換えます。列がすでに最小の minWidth である場合は、それを削除して確認してください。
2. 任意の列を取り、それをより高い minWidth フィーダーの列に置き換え、別の列を削除します。
3. 他の方法で、誰かが指摘してくれると嬉しいです。

最初の方法を正しく実装しました。以下はコードです。ただし、別の方法でコードを正しく記述することはできません。

どんな助けでも大歓迎です。

ありがとう

私は最適化について学んでおり、OpenOpt は初めてです。

それぞれに 3 つのリソース使用状況インジケーター (CPU、メモリ、ネットワーク) があるプロセスを表現したいと思います。次の制限に従って、N 個のプロセスをグループ/ビンに割り当てたいと思います。

理想的には、このタイプの出力が必要です。

質問: どうすればできますか? OpenOpt でこれを行うことができない場合、これに役立つ他のライブラリはありますか?

ここに私の初期コード: https://github.com/vonpupp/mdbp/blob/master/ksp_2.py

どうもありがとう！

私は現在、患者を配置する必要がある座席数がそれぞれ異なる複数の場所 (ビン) を持つスケジューリング ツールに取り組んでいます。患者は陽性または陰性のいずれかです。同じ場所に陽性患者と陰性患者を混在させることはできません。

患者を着席させる必要があるたびに、患者が肯定的か否定的かに基づいて、患者を座らせることができるかどうかを述べることができる必要があります.

患者の配置を流動的にできるように、患者を場所に割り当てる必要はありません。キャパシティを最大化する必要があるだけです。

計算を行う時点で、次のことがわかります。

1. いくつの場所がありますか。
2. 各場所の座席数。
3. すでに座席を与えられた陽性患者の数。
4. すでに座席を許可された陰性患者の数。

誰かがこれに対する明確な解決策を持っていると確信していますが、現時点では木に木が見えません。