問題タブ [bin-packing]

私は試験のために勉強していて、一連の練習問題が与えられました。これが私が苦労しているものです。誰かがこの問題への正しいアプローチに光を当てるのを手伝ってくれることを願っています:

これが私の最初の問題です：

決定バージョン: 決定バージョンを使用して最適なソリューションを見つけるために、はいの答えが得られるまで、さまざまな K を使用してみます。最適化されたソリューションが 7 だとしましょう。

最適なソリューションが 7 つのビンであることがわかったので、アイテムを最大から最小のサイズで並べ替え、最大から最小のビンを埋め、ビンがなくなるまでビンをループバックすることで、決定バージョンを解決します。セット内の要素。

最適解があり、決定バージョンを解きたい場合、最適解によって返されたビンの数を取得し、決定バージョンで実行して、yes が返されるかどうかを確認します。

私はこれまでこのような問題を実際に見たことがないので、適切なフォーマットがどうあるべきかわかりません.

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

スペース使用の問題に直面している、または問題にどのような名前を付ければよいかわかりません。

基本的にメッシュの問題です。

画像を使用して問題を説明しようとしました。

問題文は以下のようなものです。

1. 斜め線のボックスは、利用可能なすべてのコンテナーに収まるように、最適な比率で配布する必要があるアイテムです。
2. コンテナは異なる色で表示されます。
3. これで、すべてのコンテナが長方形になります。
4. すべてのコンテナーは、縦向きモードまたは横向きモードのいずれかで配置する必要があります。

コンテナーとアイテムの両方で幅と高さを測定できます。プログラムの場合、それらは基本的にピクセルです。

仲間のメンバーのコメントに基づいて、SpektreとLasse V. Karlsen は、ここで同じことを明確にします。

1. 二次元配置です
2. はい、コンテナーを再配置して、可能な限り最良のパターンを実現できます。
3. アイテムのどの部分も空白にすべきではありません。アイテムはコンテナの一部である必要があります。
4. アイテムはコンテナーに重ねることができ、高さと幅はコンテナーごとに異なる場合があります。また、アイテムの高さの幅もさまざまですが、形状は常に長方形のままです。
5. アイテムの位置は、左上にくっつくのが望ましいです。
6. はい、それはビンパッキングアルゴリズムに多少似ていますが、そのアルゴリズムの唯一の問題は、ビンパッキングアイテムが複数でコンテナが1つであることです。この場合、アイテムは1つでコンテナは複数です。したがって、基本的には配布の問題です。
7. アイデアは、コンテナのサイズがあり、その長方形を作成できるようにコンテナを配置する必要があるという実際の問題です。

プログラムは次の出力を与えるはずです

1. コンテナの位置
2. コンテナの中にあるアイテムの一部。
3. そしてアレンジパターン。

2 つの入力を受け取る関数が必要です。

• 幅と高さのあるバウンディング ボックス
• 幅と高さが変化する長方形のアイテムの配列 (すべてバウンディング ボックスよりも小さい)

追加のプロパティを持つ同じアイテムの配列を出力しposition（元のアイテムを変更できます）、アイテム間の距離が最大化されるようにxしyます（注-ポイント間の距離ではなく、アイテムの寸法を考慮する必要があります）。

数学的に証明された最善の解決策である必要はありません。十分なヒューリスティックで問題ありません。

私はビンパッキングを見てきましたが、それは私が望むこととは逆のようです。

疑似コードであっても、任意の言語を使用できます。

どこから始めればよいかさえわかりません。現在、位置をランダム化しているだけで、アイテムが重なってしまうことがありますが、これは望ましくありません。

3 つの製品と 5 つのボックスがあります。

寸法は次のとおりです。

すべての製品が収まる最小限の容量のボックスを選択したい.

私は次のコードを書きましたが、それらの中から 1 つのボックスのみを選択するように制約を追加する必要があることを知っています。しかし、現在の状態では機能していません(実行不可能なソルを与えています)。コードは以下で入手できます。

よろしくお願いします。

注：私は単純な問題（1D）を与えますが、実際には私の本当の問題は3Dの問題です。この場合、製品と箱の長さのみを考慮しますが、実際には幅と高さも考慮する必要があります。

data.frame/data.table の列を 3 つのグループにグループ化しようとしていますが、すべて同じ合計になります。

グループ 1 は小さな値を持つ多数の行で構成され、グループ 3 は大きな値を持つ少数の行で構成されるように、データはまず最小から最大の順に並べられます。これは、次の精神で達成されます。

成功している間は、もっと良い方法があるはずだと感じています (そして、私が見逃している非常に明白な解決策かもしれません)。

• ベクトル化されたアプローチが利用可能な場合、特にネストされたifを使用して、ループに頼るのは好きではありません-100,000以上のレコードでも、このコードは非常に遅くなります
• このメソッドは、多数のグループ (必ずしもループではなく、ifs) にコーディングするのが非常に複雑になります。
• 列の事前注文が必要です。これを回避することはできないかもしれません。

ニュアンスとして (それが違いを生むわけではありません)、合計されるデータは常に (または常に) 連続した整数になるとは限りません。