問題タブ [bin-packing]

複数の商品を発送するためのパッケージサイズを計算するための既存のソフトウェアまたはアルゴリズムを知っている人はいますか?

在庫データベースには、長さ、幅、高さの寸法が定義されたアイテムがたくさんあります。これらの寸法を考慮して、事前定義された箱のサイズに収まる購入アイテムの数を計算する必要があります。

長方形または不規則な形状の 2 次元ビン パッキング用のオープン ソース (できれば C++) アルゴリズムを探しています。この件に関するいくつかの論文を見つけましたが、コードはありません。

私は、任意の 3D ビン パッキング アルゴリズムの決定論的な実装を探しています。つまり、1 つまたは多くの大きな立方体の中に多くの小さくて異なる立方体を詰め込むためです。ソリューションは、最適なものとは異なる場合があります。

C、C++、Java、C#、IronPython、IronRuby、または .Net コードからビン化できるその他の言語で作成する必要があります。

この C アルゴリズムhttp://www.diku.dk/hjemmesider/ansatte/pisinger/3dbpp.cを見つけましたが、立方体を回転させて最適なものを見つけません。逆さまに回転しなくても大丈夫ですが、横向きに回転できるはずです。

数値のリストを同じサイズの2つの「ビン」に分割するために、First-Fit-Decreasingビンパッキングアルゴリズムを実装しました。アルゴリズムはほとんどの場合、最適なパッキング配置を見つけますが、そうでない場合もあります。

例えば：

数字のセット4、3、2、4、3、2は、明らかにこの配置に分割できます：1）4、3、2 2）4、3、2

最初の適合減少アルゴリズムは解決策を見つけられません。

この状況では、正しい解決策が存在する場合にそれを見つけられないことは受け入れられません。

元のパズルは、数列を等しい合計を持つ2つのセットに分割することです。

これは単なるビンパッキング問題ですか、それとも間違ったアルゴリズムを使用しましたか？

私は 3 次元のビン パッキングの問題に直面しており、現在どのアルゴリズム/ヒューリスティックが最良の結果をもたらしているかについて予備的な調査を行っています。問題はNP困難であるため、すべての場合に最適な解決策が見つかるとは思っていませんが、疑問に思っていました:

1) 最適な正確なソルバーは何ですか? 分岐限定？妥当なコンピューティング リソースで解決できる問題のインスタンス サイズはどれくらいですか?
2) 最高のヒューリスティック ソルバーは何ですか?
3) いくつかの実験を行うための既製のソリューションには、どのようなものがありますか?

各行の最後にハード リターンを含め、それぞれ 60 文字の長さの 3 行のテキスト (本質的にはジブリっぽい) を生成する必要があります。行は、さまざまな長さ (通常は 1 ～ 8 文字) の単語の辞書から生成されます。単語を複数回使用することはできず、単語はスペースで区切る必要があります。これは本質的にビンパッキングの問題だと思います。

私がこれまでに取ったアプローチは、長さによってグループ化された単語の hashMap を作成することです。次に、ランダムな長さを選択し、その長さの単語をマップから取り出して、現在生成している行の末尾に追加します。スペースまたはハード リターンを考慮します。約半分の時間は機能しますが、残りの半分の時間は無限ループに陥り、プログラムがクラッシュします。

私が直面している 1 つの問題は次のとおりです。行にランダムな単語を追加すると、特定の長さの単語のグループが枯渇する可能性があります。これは、辞書内の各長さの単語数が必ずしも同じであるとは限らないためです。たとえば、長さ 1 の単語は 1 つしかない場合があります。その長さの任意の単語が利用可能です。

以下は、私がこれまでに持っているものをまとめたものです。私は ActionScript で作業していますが、どの言語でもこの問題についての洞察をいただければ幸いです。よろしくお願いします。

私は、(ランダムな寸法の) ボックスをコンテナに収める方法を示すアプリケーションを作成することに興味を持っていました。実際の例は、UPS トラックのスペースを最大限に活用する方法を教えてくれるものです。このようなことを始めるのに適した場所を知っている人はいますか? 私が話していることと似たようなことをする既存のアルゴリズムはありますか?

サイズが不明なN個の長方形を可能な限り最小の長方形に合わせるのに適したアルゴリズムを誰かが知っているかどうか疑問に思っていました。

最適とは、結果の包含長方形に残る空白の量を減らすことを意味します。

これを使用して、一連の画像から CSS スプライトを生成したいと思います。

どうもありがとう、

イアン

このサイトを使用するのは初めてなので、フォーマットが不適切であったり、変な表現があったりして申し訳ありません。このサイトのルールに準拠するように最善を尽くしますが、最初は間違いを犯す可能性があります。

私は現在、STL コンテナーを使用して C++ でいくつかの異なるビン パッキング アルゴリズムの実装に取り​​組んでいます。現在のコードには、修正が必要な論理的な障害がまだいくつかありますが、この質問はプログラムの構造に関するものです。論理的な障害の数を最小限に抑え、可能な限り読みやすくするためにプログラムをどのように構築する必要があるかについて、セカンドオピニオンを求めたくはありません。現在の状態では、これが最善の方法ではないと感じていますが、現在、コードを記述する他の方法は実際には見当たりません。

この問題は、動的なオンライン ビン パッキングの問題です。アイテムが割り当てられたビンを離れる前に、アイテムが任意の時間を持つという意味で動的です。

要するに、私の質問は次のとおり
です。ビン パッキング アルゴリズムの構造は C++ でどのように見えるでしょうか?
STL コンテナは、実装で任意の長さの入力を処理できるようにするための優れたツールですか?
コンテナーを読みやすく、実装しやすい方法で処理するにはどうすればよいですか?

私自身のコードについてのいくつかの考え:
クラスを使用して、さまざまなビンのリストとそれらのビン内のアイテムのリストの処理を適切に区別します。
実装を可能な限り効果的にする。
ベンチマーク用に、さまざまなデータ長とファイルで簡単に実行できます。

これは私のコードの単なるスナップショットであり、まだ正しく実行されていないことに注意してください

関係のないおしゃべりでこれを混乱させたくないだけです。貢献してくれた人々に感謝したいだけです。コードを見直して、プログラミングをもう少しうまく構築できるようになることを願っています。

私は問題を解決しようとしています（phpでは、プログラミング言語は関係ありません）。お金を払った人がn人いて、n人が支払った金額の合計と同じ金額を支払う人がm人います。これらの人の間の送金の最短ルートを計算したいと思います。支払いを分割して、別の人に支払うことが可能です。理想は、1人が1つまたは2つのトランザクションのみを行うことです。誰かが私を正しい方向に向けたり、これを手伝ってくれるかもしれませんか？

例：Aさんが100ドルを支払った

Bさんは200ドルを支払いました

Cさんは50ドルを支払いました

Dさんは24ドルを支払います

Eさんは175ドルを支払います

Fさんは151ドルを支払います

これに対する1つの可能な解決策は

人物Eは人物Aに100ドルを支払います。

EさんはBさんに75ドルを支払います。

FさんはBさんに125ドルを支払います。

FさんはCさんに26ドルを支払います

DさんはCさんに24ドルを支払います