問題タブ [knapsack-problem]

表面上は0-1ナップザックのように見えるという問題があります。私は選択できる（または選択できない）可能な「候補」のセットを持っています。各候補には「重み」（コスト）と潜在的な「価値」があります。これが全体の問題だったとしたら、私はDPアプローチを使用して、それで終わります。しかし、ここにカーブボールがあります。最終的な解決策に含まれる可能性のある候補には、「パーティション化の制約」があります。

つまり、候補空間は離散同値類に分割されます。私の特定の問題については、約300の候補と12の可能な同値類があります。クラスC1の候補者は3人、C2の候補者は6人までしか持てないという「ビジネスルール」などがあります。

この制約は、分枝限定法または他の形式の剪定を使用したグラフ検索タイプのアプローチを示唆していますが、0-1ナップザックのDPソリューションに精通しているだけなので、どのように開始するかについて少し困惑しています。この問題にはどのような手法/アプローチが適しているでしょうか？また、制約プログラミングライブラリを使用することも考えましたが、解決策を見つけることができるかどうかわかりませんか？

私は最初のプログラミングコースにいて、今かなり行き詰まっています。基本的に、テキスト ファイル (コードの 1 行目) から 16 個の値を取得し、コードの 2 行目に 1 つの値があります。これらの 16 個の値を配列に読み込み、その 2 行目の値をターゲットとして設定します。その部分については問題ありませんでした。

しかし、私が問題を抱えているのは、ビットマップを作成して、ターゲット数に等しい 16 の値のすべての可能なサブセットをテストすることです。

IE、これらの数値があったとします。

次に、各値をビットマップに対応させます

次に、「1」で述語された値のみを受け入れます

次に、そのサブセットをテストして、「ターゲット」数と等しいかどうかを確認します。

問題で使用できる配列は 1 つだけで、数学クラスは使用できません (まだ取得していません)。

私は概念を理解しており、シフト演算子と論理記号を実装する必要があることを知っていますが、&本当に途方に暮れています。私はとてもイライラしていて、誰かが私に何かヒントをくれるかどうか疑問に思っていました.

Scala の各項目の 1 つを使用して境界付きナップザックの問題に対する回答を書き、次の結果で Haskell に転置しようとしました。

コードをクリーンアップする方法に関するヒントを探しているのではなく、コードを機能させるためだけです。私の知る限り、次のことを行う必要があります。

• タプルオプションごとに (ys で)
  • 現在のタプル (y) と現在の合計 (xs) を合わせた重みが容量より小さい場合
  • 使用可能なタプル (ys) から現在のタプルを引いたものを使用して、現在のタプルと現在の合計 (xs) を含む最適なナップサックを取得します。
• 最後に、これらの結果の中で最も価値のあるものを取得して返します

*編集: *申し訳ありませんが、何が問題なのかを言い忘れました... コンパイルは問題なく実行されますが、間違った答えが返されます。次の入力について、私が期待するものとそれが生成するもの：

それで、私は矛盾の原因が何であるか疑問に思っていましたか？

sepp2k のおかげで解決策:

上記の期待される結果を返します。

ナップサック問題のブルートフォース実装を作成する必要があります。擬似コードは次のとおりです。

アルゴリズムの実装はかなり簡単ですが、Sのべき集合を生成し、そのべき集合のサブセットをwhileループの各反復にフィードする方法については少しもわかりません。

私の現在の実装では、ペアのリストを使用してアイテムの重量と利益を保持しています。

そして、computeMaxProfit関数用にこのリストのべき集合を生成したいと思います。リストのサブセットを生成するためのアルゴリズムはありますか？リストは使用するのに適切なコンテナですか？

ナップザック問題に関するウィキペディアの記事には、3 種類のリストが含まれています。

1. 1-0 (タイプの 1 つのアイテム)

2. 有界 (同じタイプの複数のアイテム)

3. Unbounded (同じ種類のアイテム数に制限なし)

この記事には、1. と 3. の種類の問題に対する DP アプローチが含まれていますが、2. の解決策はありません。

2. を解くための動的計画法のアルゴリズムはどのように記述できますか?

加算問題の再帰的解法に問題があります。問題は次のとおりです。与えられた m と n に対して、最小数が使用されるように n 個の数を m に合計するプログラムを作成します。ユーザーは n、m、n の数字を入力します。例: m=19 n=4 8,5,4,1 . 解は 8+5+5+1 です。配列内の次の数値で関数を呼び出し、合計よりも小さいうちに追加すると、配列内の次の数値の合計が m になる場合にのみ解が見つかります。問題が次のような場合: m=28 n=3 8,7,5 解決策は 8+8+7+5 ですが、私のプログラムは 8+8+8 になり、7 または 5 を追加しようとしてクラッシュします。それらのうち、最大 28 に収まる可能性があります。したがって、ここでの問題は、2 ステップ以上前に戻ることです。8+8+8+7 から 8+8+8 に変更できますが、8+8 に戻ることはできません。これはナップザック問題に似ていますが、より単純です。これまでに私のコードを含めて申し訳ありません：

出力に問題がありますが、それは今のところ重要ではありません。

このタイプのアルゴリズムを検索し、多くのものを赤くしましたが、探しているものを正確に見つけることができませんでした。

だから、私は買い物に行くつもりで、私は x のお金を持っています。私のトラックは最大 y の重量を運ぶことができ、各アイテムには重量と価格のボーナスクレジットがあります。出力は、選択したアイテムの総重量がトラックの容量と私が費やさなければならないお金を超えないように、取得できる最大のボーナスクレジットを与える必要があります!

アルゴリズムの名前を知っていますか？どのように進めればよいですか？私はCでそれをしなければなりません！

ありがとう ！！

これは複数のナップサック問題のバリエーションかもしれないと思います（あるいはそれに減らすことさえできるかもしれません）が、私にはわかりません。ここに問題があります：

既知の値と重みを持つアイテムのセットがあります。また、ナップザックのセットがあり、各ナップザックは固定数のアイテムを保持できます（異なるナップザックは異なる数のアイテムを保持できる場合があります）。与えられた重量の下にとどまりながら、ナップザックのアイテムの合計値を最大化します。

個々のナップザックには重量制限がないことに注意してください。各ナップザックには、「含めることができるアイテムの数」の制限のみがあります。他の唯一の制限は、アイテムの総重量です。

何か案は？？（もちろんブルートフォース以外）。前もって感謝します！:)

編集：私が含めるのを忘れた1つの重要な制限：

アイテムは必ずしもバッグに入れることができるとは限りません。互換性のないバッグに入れると、基本的に値はゼロになります。各アイテムの値がバッグに依存する一般的なケースを想像できますが、私の場合、その値はバッグに応じて0または通常の値になります。