問題タブ [subset-sum]

これは問題のステートメントです：

整数のリスト L と整数 S が与えられた場合、要素の合計が S になるすべてのサブリストを生成します。

これが私の解決策です：

したがって、それを実行してゴールを求められた後getsub([1,2,5,6],X,7) 、要素の合計が7になるすべてのサブセットを取得しようとしましたが、チェック句No Solutionの変数に関する警告とLR、変数はバインドされていません。何が間違っているのか、またはこれに対するより簡単な解決策があるかどうかはわかりません。どんな助けでも大歓迎です。

私は、ナップザック/サブセット和問題の特殊なケースに対処しなければならない問題に取り組んでいました。問題は次のとおりです。

次のようなランダムなサイズが減少する一連のバンドル サイズがあります{47, 35, 22, ...}。#widgets = 33 のようなウィジェットの数量の値があります。バンドルのウィジェットの数を構成できるバンドルの最小数を見つけます。数量に等しいセットを返す方法がない場合は、null を返します。

• 例 1:
  • バンドル サイズ: 46、25、12、4、3
  • 数量: 30
  • 戻り値: {46:0, 25:0, 12:2, 4:0, 3:2} (バンドルサイズ:バンドルの数)
• 例 2:
  • バンドル サイズ: 46、25、12、4、3
  • 数量: 17
  • 戻り値: {46:0、25:0、12:0、4:2、3:3}
• 例 3:
  • バンドル サイズ: 46、25、12、4、3
  • 数量: 47
  • 戻り値: {46:0、25:1、12:1、4:1、3:2}
• 例 4:
  • バンドル サイズ: 46、25、12、4、3
  • 数量: 5
  • 戻り値: null

この問題をどうするか。

C# でプログラムを作成しました。このプログラムは、十分なジョブを閉じますが、for ループでインデックスをリセットして、残りのセットでは機能しないバンドル サイズをダンプします。それがどこまで進むかについて要求された場合、ソースを投稿します。

要求されたコード:

これは、アルゴリズムの最終試験の問題でした。教授が試験のコピーを家に持ち帰らせてくれたので、そのままです。

1. (20 点) I = {r1,r2,...,rn} をn 個の任意の正の整数の集合とし、Iの値を区別します。 私は任意のソートされた順序で与えられていません。I 'のすべての要素の総和が正確に 100*ceil(n^.5) になるような I のサブセット I' を見つけたいとします ( I の各要素はI 'に最大1回現れることができます)。この問題を解決するための O( n ) 時間アルゴリズムを提示します。

私が知る限り、それは基本的にナップザック問題の特別なケースであり、サブセット和問題としても知られています...どちらもNPにあり、理論的には線形時間で解決することは不可能ですか?

それで...これはひっかけ問題でしたか？

この SO 投稿では、基本的に、重みが制限されている場合は疑似多項式 (線形) 時間近似を行うことができると説明していますが、試験問題では重みが制限されておらず、どちらにしても試験の全体的な難しさを考えるとショックを受けるでしょう教授が、あいまいな動的最適化アルゴリズムを知っている/考え出すことを期待していた場合。

私はキーとしてメニューディクテーションアイテムを、値として価格を持っています。単品よりも少し安くなる商品の組み合わせもあるかもしれません。エクサの場合：

ここで、いくつかのアイテムを注文したと仮定すると、出力は指定された注文の最小量になります。

これが私がジェネレーターとして使用するすべての価格で試したコードです:

しかし、これを実行すると、タイプエラーが表示されます:

ここに表がありますT:-

以下は架空のSQLです

期待される結果は次のとおりです:-

(ア)

(ロ)

(ハ)

「A」ケースが最も好ましいです。

このケースが組み合わせに関連していることは知っています。

現実の世界では、クライアントは店から商品を受け取り、彼と店の間の合意により、毎週金曜日に支払います。支払い額はアイテムの正確な合計ではありません。たとえば、彼は 50 ユーロ ( = 250 ユーロ ) の本を 5 冊受け取り、金曜日に 150 ユーロを持ってきたので、最初の 3 冊の本は完全に一致します - 3 * 50 = 150.これらの 3 冊の本の ID を見つける必要があります。

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

与えられた方程式

2(p ₁ ) + 3(p ₂ ) + 7(p ₃ ) >= 257のように

_{p 1}、p ₂、p ₃のすべての可能な組み合わせを見つける必要があります。これにより 、上記のステートメントが真になり、結果の合計 (方程式の左側) がすべての x _nが既知の場合に最小になります。

のような一般的なケースのアルゴリズムを調べてみました

(x ₁ )(p ₁ ) + (x ₂ )(p ₂ ) + (x ₃ )(p ₄ ) + ... + (x _n )(p _n ) >= ターゲット

そして、ナップザック問題とサブセット和アルゴリズムの解決策に出くわしましたが、それらはこの問題とまったく同じではありませんでした。

_{p n}の下限値を持つ Python 3.x のアルゴリズムを使用する前に試してみましたが、それでも O(とんでもない) 時間の複雑さで実行されます。

明らかに、ここでの数はすべて自然数であり、そうでなければ無限の解が存在します。

数値の配列と配列要素を合計する合計のリストがある場合、どの要素が合計に含まれているかを判断するための最も効果的なアプローチ (または少なくともブルート フォース ハックではない) は何ですか?

簡単な例は次のようになります。

配列 = [6, 5, 7, 8, 6, 12, 16] 合計 = [14, 24, 22]

そして私は知りたい：

14には8、6が含まれます

24 には 5、7、12 が含まれます

22には6、16が含まれます

http://jsfiddle.net/tTMvP/

常に少なくとも 1 つの正しい答えがあることを知っています。数字がチェックアウトされることだけが重要です。重複があるインデックスをペアにする必要はありません。合計に関連する値だけです。このような問題を解決するための確立された機能はありますか?

これは、私がソリューションを書いている言語であるため、javascript の質問にすぎません。これは、Javascript でフィルタリングされた一般的な数学関連の質問です。これが適切なフォーラムでない場合は、適切なスタック交換サイトへのリダイレクトを歓迎します。

最終的にTrueが返されたときに見つかった値を出力できるように、サブセット合計の問題のコードを変更する方法を見つけようとしています。私の現在の実装は再帰的に機能し、メモ化を利用していますが、それを変更して保存し、最終的に目的の合計に達するパスを返す方法がわかりません。

私はそれの再帰性を破棄し、代わりに反復を使用しようとしましたが、次の値を使用しない場合と使用する場合の両方を処理するために、for ループ内でコードをレイアウトする方法がわかりませんそれ。

注：この実装では、値は一度しか使用できません。元の「サブセット合計」の問題がそれを強制するかどうかはわかりません...

これを変換する方法に関するヘルプやヒントは大歓迎です。今後のインタビューの練習としてこれをやっています。