問題タブ [knapsack-problem]

重みが W1...W4、値が V1...V4 の項目 I1、I2、I3、I4 があります。最小の重みで値を最大化したい。これは伝統的なナップザックです。ただし、一部のアイテムは一緒に使用できないという小さな制約があります。したがって、I2 と I3 は一緒に使用できないとしましょう。誰でも動的プログラミングソリューションまたは同じソリューションの他のソリューションを提供できますか?

この問題で使用される可能性のあるサブセット合計を生成するプログラムを作成しました。

$1 コインが 3 枚、$2 コインが 2 枚、$5 コインが 3 枚、$10 コインが 1 枚あるとします。これらのコインから $10 を得る方法は 4 つあります。$X1 コインが n1 枚、$X2 コインが n2 枚.... nm $Xm 枚ある場合、これらの限られた数のコインから $X を取得するには、何通りの方法がありますか?

{ X1, X1..... X1, X2, X2.......... X2, ..., ..., ........... .., Xm, Xm... Xm} を実行し、サブセットの合計を実行すると、確かに $X の結果が得られます。しかし、セット {n1, n2, n3.... nm} 、 {X1, X2, X3.... Xm} を使用する方法が見つかりませんでした。ナップザック問題の一種だと友達に言われましたが、どうしてかはわかりません。

これは私が書いたものの部分的なコードです:

もう少し丁寧に説明していただけると助かります。

編集:この質問は、コンピューター サイエンスの stackexchange に適していますが、私の古い質問なので、ここで編集しています。

この問題は、包含除外の原則で解決できます。コインの値は固定されているが、各コインの数はクエリごとに異なる場合に便利です。

way [v]が$x1、$x2、.. $xmで$vを作成する方法であり、それぞれが必要な回数だけ使用されるとします。ここで、 $x1 の n1 個のみを使用している場合、少なくとも( n1 + 1) 個の $x1 (実際には [ v - (n1 + 1)x1 ] の方法) を使用して構成を減算する必要があります。さらに、$x2のn2個だけを使用している場合は、ウェイ[ v - (n2 + 1)x2 ] も減算する必要があります。

ここで、少なくとも ( n1 + 1) $x1および ( n2 + 1) $x2が使用される構成を 2 回減算したため、ウェイを追加する必要があります[ v -(n1 + 1)x1 - (n2 + 1) x2 ] など

特に、

N = すべてのコインができるだけ多く使用される構成のセット、

Ai = 1 <= i <= mの場合、少なくともni + 1 個の$xiが使用される構成のセット

求めている結果 = | ん| - | A1 | - | A2 | .. - | 午前| + | A1とA2 | + | A1とA3 | + ... - | A1とA2とA3 | .....

無制限のコインで構成の数を計算するコードは、実際にはより単純です。

JaCoP 制約プログラミング ライブラリの使い方を独学で学ぼうとしていますが、0/1 ナップザック問題の実装に少し苦労しています。問題サイズ 4 を試し、項目と変数を次のように定義しました。

次に、ナップザック リストを使用してナップザック制約を追加しました。

Constraint con = new Knapsack(knapsack, knapsackCapacity, knapsackProfit); store.impose(con);

そして、チュートリアルに記載されている方法で解決策を検索しました。

私が得た結果は、すべての量がゼロであり、制約は満たしていますが、何も最適化していないということです。各アイテムの利益 * 数量を最大化するために、別の制約または追加する必要があるものはありますか?

ありがとうございました

ベン

すべての利益が 1 に等しい場合のナップザック問題のバリエーションがあります。古典的な離散 (0-1) ナップザック問題よりもはるかに速く解決できるようですが、どうすればよいでしょうか? 貪欲なアルゴリズムだけが機能しますか (反復ごとに最小重量のオブジェクトをナップザックに入れます)?

これは難しいアルゴリズムの問​​題です：

リストを2つの部分（合計）に分割し、それらの合計が（最も）互いに最も近いものにします

リストの長さは1<=n <= 100であり、それらの（数）の重みは1 <= w<=250です。

例：23 65134 32 95123 34

1.sum = 256

2.sum = 250

1.list = 1 2 3 7

2.list = 4 5 6

アルゴリズムはありますが、すべての入力で機能するわけではありません。

1. 初期化。リストlist1=[]、list2 = []
2. 要素の並べ替え（指定されたリスト）[23 32 34 65 95123134]
3. 最後の1つをポップ（最大1つ）
4. 違いの少ないリストに挿入

実装：list1 = []、list2 = []

1. 134挿入リスト1を選択します。list1 = [134]
2. 123挿入リスト2を選択します。list1に挿入すると、差が大きくなるためです
   。3. 95を選択し、list2を挿入します。sum（list2）+ 95-sum（list1）が小さいためです。

等々...

ゲームを開発していて、パッキングの問題に似たコンポーネントのレイアウトを処理するために解決しなければならない問題を見つけました。

何をする必要があるかを要約すると、次のようなスペースがあるとします。

すべての角のセルは 4x4 で、中央のセルは 3x3 です (残りのセルは 3x4 と 4x3 です)。次に、1x1 から 3x3 まで変化するこれらのブロック内に配置する一連の要素があります (4x4 はまだ必要ないと思いますが、何も変更しないはずです)。もちろん、これらの要素は境界線を越えることはできず、完全に 1 つのブロック内に配置する必要があります。

それらを割り当てる最良の方法はどれですか? 必要がない場合は、それらをすべてくっつけたくない場合を想定します (たとえば、2 つの要素を離して配置するのに十分なスペースがある場合は、2 つの要素を一緒に配置しないでください)。状況がかなり限られているため、単純なアルゴリズムを探しています..

おまけの質問: これらの 9 個のブロック (おそらく他の 3 ～ 4 個) に加えて、他のブロックがあると仮定すると、新しいブロックと比較してこれらのブロックを優先するにはどうすればよいでしょうか? (つまり、塗りつぶしのしきい値に達するまで、追加のブロックを使用しないということです)。

もちろん、私は一般的なアイデアを探していますが、実装はありません:)

KnapsackDPで解決できる一方で、NP完全であることはわかっています。pseudo-polynomial彼らは、「入力の長さ」（つまり、入力をエンコードするために必要なビット数）が指数関数的であるため、DPソリューションは であると言います。残念ながら、私はそれを取得しませんでした。誰pseudo-polynomialか私にそのことをゆっくり説明してもらえますか?

動的計画法でナップザック0-1の問題を解決する方法は知っていますが、O（N * C）（Nアイテム、C容量）の複雑さを損なうことなく、どのアイテムを取るかを判断するのに苦労しています。

何かアイデアはありますか（ボトムアップアプローチをお勧めします）？

アイテムのセット（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 目標がどのように関連しているかに関する情報を使用して説明を作り直し、ビンの優先度の変数を削除しました。これは、回答を見つける可能性が低くなり、作業中のシステムの他の場所で回避できるためです。

バックトラッキング関数に問題があり、特定のデータでループします。プログラムコード全体をここに書くことはできませんが、関数をここに置くことはできます。

ここに説明があります：

quantity - 値配列内の要素
の数 values -数値の配列
index - 再帰を制御する
変数 moneyA - 配列値の要素の合計を格納する変数half -
再帰が行われた後に moneyA が到達する必要がある数値
配列値を参照します

この関数は、長さの値の配列である要素の数量を取得します。値は、数値を含む配列を最高のものから最低のものに並べ替え、インデックスは再帰を制御し、デフォルトは 0 であるため、最初の要素から開始します。money からの数値を格納する変数値配列と、値配列から合計された数値の半分である半分に達する必要があり、ifChosen は選択された数値を格納します。

関数全体がこれを行い、values 配列の要素を合計し、半分未満の場合は半分に達したかどうかをチェックし、それを moneyA に追加し、ifChosen でマークしてから、合計が半分より大きい場合は次の要素に進みます戻り、ifChosen 配列でマークを外し、moneyA から減算します。常に最高の要素を取得する必要があります。

簡単な例を次に示します。

この結果は次のようになります。

もちろん、この単純な例では素晴らしい仕事をしますが、より多くの数字を持ち、1 つの数字が複数回出現するより複雑な例では、ループして再帰が停止しません。私は実際にこれに1.5週間取り組んでおり、すべての友人に尋ねましたが、何が問題なのか誰も知りません. ナップザックの問題と少し関係があることは知っていますが、まだそれを持っていないので、まだ勉強する必要があります.

役立つ回答をお待ちしております。

句読点で申し訳ありませんが、私は初めてここに来て、フォーマットに慣れていませんでした。

ここに1つの例があります：

今、私はそれが永遠にループすると思うもの: 43 要素:

@Karl Bielefeldtはい、非常に多くの組み合わせがあることを知っているので、速度を上げようとしています。今のところこれですべてですが、特定の入力に対して間違った結果が得られます。誰でもそれを修正できますか?以前よりもはるかに高速に動作しますか?