問題タブ [subset-sum]

ガーディアン（英国の新聞）の今日の版では、クリス・マスランカによる43ページの「ピルジックパズル」セクションで、次のパズルが与えられました。

東方の三博士は...クリスマスの買い物をするためにハロッズに行きました。キャスパーはゴールドを購入し、メルヒオールはフランキンセンスを購入し、バルタザールはデイリーミルラのコピーを購入しました。レジ係は、これらのそれぞれのコストのユーロ数を利用し、3つの数値を加算することを意図していましたが、代わりにそれらを乗算しました。...驚異的なのは、結果がまったく同じであるということでした：€65.52。3つの合計は何でしたか[彼は3つの数字を意味していると思います]？

私の解釈は次のとおりです。a+b+ c = abc = 65.52（正確に）となるようなa、b、cを見つけます。ここで、 a 、 b 、 cは小数点以下2桁以下の正の小数です。したがって、 a、b、およびcも65.52（約）未満である必要があります。

したがって、私のアプローチは次のとおりです。a、b、およびcのすべての候補セットを見つけます。ここで、a + b + c = 6552であり、 a、b、およびcは{1 ... 6550}からの整数です（概念的には、すべてのオペランドを乗算しました便宜上100ずつ）。次に、すべての候補セットについて、すべてのオペランドを100で除算し、それらを乗算することによって（任意精度の演算を使用して）、他の条件を満たすのは簡単です。

これは、私が見ているように、サブセット和問題のインスタンスです。そこで、ダーティ（指数時間）アルゴリズムを実装しました。これにより、a = 0.52、b = 2、c=63という1つの明確な解決策が見つかりました。

サブセット和問題にはもっと良いアルゴリズムがありますが、これは平均的なGuardianリーダーには少し手が届かないものになっていると思いませんか？

40ページに答えがリストされています：

これは試行錯誤で簡単です。デイリーミルラの52pを推測します。しかし、0.52を掛けると、およそ半分になるので、1つの合計が約2になる必要があります。したがって、2 X 63X0.52を試してください。Etvoilà。この答えはユニークですか？

まあ、私たちは答えがユニークであることを知っています（2、63、0.52の他の順列を無視して）。

私が知りたいのは、どうすればこれを「簡単」にできるのかということです。パズルを部分和問題のインスタンスとして特徴づけるのは正しいですか？ソリューションを簡素化するために利用できるパズルのいくつかの特徴を見落としていませんか？誰かが同様の「試行錯誤」のアプローチを採用することができましたか？もしそうなら、彼らは私をそれを通して連れて行くことができますか？クリス・マスランカは、NP完全問題に単純に臆することはありませんか？

部分和問題を学んでいたので、ここで質問したいのですが

（1）サブセット和アルゴリズム

このリンクのCコードを今読んだのですが、なぜ作者が定義できるのでしょうか。

S[i,0]subset[1,...i]合計すると、0なぜ割り当てられるtrueのでしょうか。サブセットのコンテンツを出力する場合、このアルゴリズムを変更するにはどうすればよいですか。著者と個人的にチャットすることは禁じられているようだったので、投稿する必要があります。

S[i,0]（2）配列に負の数がある場合、それが適合しないことをテストしようとしました。との初期値を定義するにはどうすればよいS[0,j]ですか？

誰かが私が明確にするのを手伝ってもらえますか？

前もって感謝します！

SOにはサブセットサムの質問と回答がたくさんありますが、どういうわけか私は特定の問題の解決策を見つけることができません.

長さ n のトラックを作成するには、トラック セグメントの数と長さを見つける必要があります。セグメントの長さ: 8, 10, 12, 14, 16, 18, 20, 22, 24 フィート 数量は最大 4 セグメントです トラックの長さは ~ 20 ～ 100 フィートです (常に偶数)

これは本物のトラックです。セグメントの順序は関係ありません。ただし、好ましいサイズの組み合わせがあります。大きい/小さい組み合わせよりも、すべて同じ長さまたは互いに近い方が優先されます。

すなわち:

• 70 => 20,20,20,10 は簡単に選択できますが、16,18,18,18 が優先されます
• 60 => 20,20,20 は 14,14,14,18 よりも優れています

必要に応じて、さらに例を挙げることができます。

私は 1 つの最適なソリューションを探しているのではなく、考えられる最適なソリューションの小さなセットを探しています。最終的には人が選択しますが、これは最良の選択肢の提案に関するものです。

これまでに行ったことは次のとおりです。それは機能していますが、複雑な方法のようです。

この投稿Algorithm to find which numbers from a list of a list of size n sum to another numberから基本的なアルゴリズムを採用しました。このコードで変更したのは、整数に変えることだけです。可能なすべての組み合わせを返します。5曲以上まで。

結果セットをさらに減らすために、いくつかのLinqを実行します

このコードは次の結果を生成し、60 で実行します

または80でこれ

したがって、私の最終結果 (4&5) は、実際には必要なものに近いものです。

しかし、考えられる 3 トラック ソリューション、場合によっては 2 トラックについても、同じコードを再度コーディングする必要があります。

次に、結果を互いに比較する必要がありますか（どういうわけか、方法がわからない）。これらすべてが、何かが足りないような気がします。それは複雑に感じます、それは間違っていると感じます。私は何が欠けていますか？

そもそも間違ったアルゴリズムを使用していますか? 彼らは私の問題を解決するのに優れていますか？

すべて正で、数値 N より小さいことがわかっている要素を含む配列があるとします。

すべての要素の合計が正確に N になるサブセットが配列内にあるかどうかを調べるアルゴリズムの一般的で高レベルの説明を誰かが教えてくれませんか?

特に効率的である必要はありません。私が扱っているセットは非常に小さいです。

私はコイン1、2、4、10、20、40、100、200、400、1000、2000セントのセットを持っています。特定の金額（<= 6000）を支払う方法がいくつあるか知りたいです。C ++での私の現在の解決策は、動的計画法を使用することです。

しかし、私の出力は正しくありません：-956301262。オーバーフローの問題が原因ですか？

Backtracking大学でアルゴリズムを学び始めたばかりです。どういうわけか、部分和問題のプログラムを作成することができました。正常に動作しますが、プログラムがすべての可能な組み合わせを提供していないことがわかりました。

例：目標の合計には100の組み合わせがあるかもしれませんが、私のプログラムは30しか与えません.コードは次のとおりです。誰かが私の間違いを指摘してくれると助かります。

プログラムを実行すると：

4、8も解決策ですが、私のプログラムでは表示されません。入力数が 100 以上の場合はさらに悪化します。少なくとも 10000 の組み合わせがありますが、私のプログラムは 100 を示しています。

私が従おうとしているロジック：

1. サブセットの合計がターゲットの合計以下である限り、メイン SET の要素をサブセットに取り込みます。
2. サブセットの合計に特定の数を追加すると、それがターゲットよりも大きくなる場合、それは取りません。
3. セットの最後に到達し、答えが見つからない場合、セットから最後に取得された番号を削除し、削除された最近の番号の位置の後の位置にある番号を調べ始めます。（配列「s」に保存するのは、メインSETから選択した番号の位置であるため）。

私は C++ を初めて使用し、ユーザー定義の数値セットを使用するサブセット プログラムの合計を作成しています。最初の数値は合計と見なされます。DDD を使用してこのプログラムをデバッグしようとしましたが、引き続き範囲外エラーが発生します。なぜこれが起こっているのか分かりません。手がかりはありますか？ありがとう。エラーは次のとおりです。

コード：

.

.

.