問題タブ [knapsack-problem]

私が問題を抱えている質問は次のとおりです。
私が与えられた重量の貯金箱を持っていて、与えられたコインのセットを使ってそこにお金を節約しているとしましょう。最後に、私は貯金箱の総重量と私が使用していたコインの重量と価値を知っています。

貯金箱に入れることを保証できる最低金額、つまり最悪のシナリオを知りたいです。たとえば、次の場合：

• 総重量=100
• 使用したコインの重さ={1、50}
• コインの価値={1、30}

その場合、私が保証できる銀行の最小値は60です。

質問はナップザックの変種ですが、正しい再発を見つけることができません。

前もって感謝します！

さて、これは古い 0-1 ナップサックの問題ですが、取得できる合計最大価格を見つけた後、持ち運べるアイテムを見つける必要があります。ただし、次のテストケース（合計3項目）の場合

ここでは、最大価格は 56です10(5+5)。どちらも同じ価格ですが、10 kg よりも 6 kg の商品の方が明らかに実現可能です。dp 行列からこれを計算する方法を教えてください。このテスト ケースの次のマトリックスを取得しました。

このアルゴリズムを使用すると、重量は 10 になりますが、最適は 6 kg です。

私は動的プログラミングが初めてで、SPOJ (http://www.spoj.pl/problems/KNAPSACK/ )で整数ナップザック問題を試しました。ただし、特定のテストケースでは、私のソリューションは正しい出力を提供していません。私による次の実装が正しいかどうかを提案していただければ幸いです。変数backはバックトラック用であることに注意してください。これについてはどうすればよいかわかりません。バックトラッキングの実装にもご協力いただければ幸いです。ありがとう。

正しい入出力テスト ケースは次のとおりです。

ただし、得られる出力は17.

制約のある 0/1 ナップサック問題の解決策を実装する必要があります。ほとんどの場合、私の問題には変数がほとんどありません (~ 10-20、最大で 50)。

多くの場合、ブルートフォースよりも優れたパフォーマンスを発揮する多くのアルゴリズムがあることを大学から思い出しました（たとえば、分枝限定アルゴリズムを考えています）。

私の問題は比較的小さいので、ブルートフォースとは対照的に洗練されたソリューションを使用すると、効率の点でかなりの利点があるかどうか疑問に思っています。

役に立ったら、私は Python でプログラミングしています。

私は動的計画法が初めてで、最初の DP 問題を試しました。問題文は

サイズ C のナップザックと、値 v[] を持つサイズ s[] の n 個のアイテムが与えられた場合、ナップザックに入れることができるアイテムの容量を最大化します。項目は何度でも繰り返すことができます。(重複するアイテムは許可されます)。

再帰関係を定式化してDPテーブルを作成し、最終的にナップザックに入れることができる最大値を取得することはできましたが、必要な合計を取得するためにどの値を選択する必要があるかを取得する方法を考案することはできません. .

これが私の解決策です：

私の解決策では、選択された最大値アイテムの位置をベクトルに保存し、最終的にそれらを印刷しようとしました。ただし、これでは正しい解決策が得られないようです。

プログラムを実行すると、以下が生成されます。

出力に示されているように、サイズ 0 の項目がないため、出力の数値が選択された項目のサイズではないことは出力から明らかです。

私のロジックまたは実装でエラーを見つけるのを手伝ってくれることを願っています。ありがとう。

あらかじめ決められたサイズの 2D 配列と、そのスペースに収まる番号付きの四角形のリストがあります。これらの各長方形には、既知の固定の高さと幅があります。2D 配列は、すべての四角形を快適に収めるのに十分な大きさであることが保証されています。

これらの各長方形を配列にランダムに配置して、重ならないようにし、すべてが配置されるようにする必要があります。それらは任意の方向に配置できます。戦艦のゲームに自分の船を配置することを想像してみてください。船のサイズがより多様で、グリッドがはるかに大きくなっています。

完成した配列は次のようになります: (0 は空のスペースを表し、ゼロ以外の数値は四角形の数値を表します)

0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 4 4 4 0
0 1 1 0 2 2 2 2 2 0 0 0 4 4 4 0
0 1 1 0 2 2 2 2 2 0 0 0 0 0 0 0
0 2 2 2 2 0 0 0 0 0 0 0 0
0 2 2 2 2 0 5 5 0 0 0 0
0 3 3 3 3 3 0 0 0 0 5 5 0 0 0
0 3 3 3 3 0 7 7 7 5 5 6 6 0 0
0 0 0 0 0 7 7 5 5 6 6 0 0

私が検討した 1 つのアプローチは、四角形ごとに、ランダムな配置と方向を選択し、それをマトリックスに配置しようとすることです。以前に配置されたブロックとの衝突が検出された場合は、再試行してください。これはおそらく最も簡単に実装できますが、あまり効率的ではないようで、明確に決定論的な方法で終了しません (リストの末尾近くの長方形は、以前に生成されたブロックとかなりの時間衝突し続ける可能性があります)。

後の長方形を配置するのにそれほど問題にならない、これを行うためのより良い方法はありますか?

問題が発生しました。できるだけ簡単な言葉で説明します。

PHP と MySQL の組み合わせを使用して、次のロジックの問題を解決する必要があります。これは、必要なものの単純化されたバージョンですが、簡単に言えば、ロジックは同じです。

ボックスだと思います。小さな箱がたくさんあり、大きな箱が 1 つあります。たくさんの小さな箱を使って大きな箱を埋めることができる必要があります。

それでは、これを分解しましょう。

次の行を持つMySQLのテーブルがあります

このテーブルは、同じサイズのボックスを使用して、数百まで実行できます

例として、サイズ 800 の 1 つの大きなボックスを、表にある small_boxes のすべての組み合わせで満たす必要があります。大きなボックスは、ユーザーが入力したい任意のサイズにすることができます。

ここでの目標は効率ではありません。たとえば、許容値内で収まる可能性のあるボックスのさまざまなバリエーションを示すだけで、わずかに下回ったり、少し上回ったりすることはあまり気にしません。

可能であれば、PHP/MySQL でこの問題に取り組む方法を理解したいと思います。私はどちらもかなり有能ですが、問題は私がこれにどのようにアプローチするかにあります.

例は素晴らしいでしょうが、私が始めるために少しの情報で喜んで解決します.

多目的/多目的サブセット和問題の高速な解決策を探しています。

追加の制約（IMOの計算を少し簡単にする）として、合計に含まれるすべての値が正であり、すべて既知の制限値にバインドされていると想定できます。

私は、1つの目的のサブセット和問題に対してO（NK）疑似多項式ソリューションがあることを知っています。私は、ウィキペディアとこのスタック交換の回答に基づいたソリューションを実装しました。

この問題を別の方法で説明すると、限界がわかっている正の数が2セットあります。最初のセットの値Aごとに、合計がAになる2番目のセットの値の組み合わせがあります。最初のセットのすべての値が、2番目のセットに関連付けられた対応する競合しない値の組み合わせを持っていることをアプリオリに知っています。 2番目のセットのどの要素が最初のセット値のそれぞれに関連付けられているかを計算するための既知の高速な方法はありますか？

サイズ n の数のセットがあります (n > 100 と仮定)。

ハードリミット x もあります。

私が望むのは、セットから可変数の要素を取得し、これらの要素の組み合わせを見つけて、合計すると合計が <= x になるようにすることですが、可能な限り x に近づけることです。

明らかに私はブルートフォースアプローチをしたくありません.この問題を解決する効率的なアルゴリズムはありますか?

分岐と境界を使用して、このナップザックの問題を C++ で実装しようとしています。この Web サイトには Java バージョンがあります: Implementing branch and bound for knapsack

私のC++バージョンで本来あるべき90を出力しようとしていますが、そうではなく、5を出力しています。

誰がどこに何が問題なのか知っていますか?