問題タブ [subset-sum]

部分和の問題に関連する問題があり、その違いによって問題が解決しやすくなるかどうか、つまり妥当な時間で解決できるかどうか疑問に思っています。

値 V、集合サイズ L、数列 [1,N] S が与えられたとき、S のサイズ L のサブセットの合計が V 未満になるのはいくつですか?

これは、次の 3 つの点でサブセット和問題とは異なります。

1. 等しいサブセットの数ではなく、与えられた値よりも小さいサブセットの数を気にします。
2. サブセットのサイズは固定されています。
3. 存在するかどうかだけでなく、合計が V 未満になるセットの数を気にします。

これを解決する合理的に効率的なアルゴリズムはありますか?

編集: 明らかに、これは組み合わせ生成アルゴリズムを使用して O(N choose L) で実行できます。私が本当に興味を持っているのは、それを大幅に高速化する巧妙なハックです。

整数の 2 つのセット (正と負の両方) を取り、それぞれの中で同じ合計を持つサブセットを見つけることができるアルゴリズムを探しています。

この問題は、サブセットの和の問題と似ていますが、両側でサブセットを探している点が異なります。

次に例を示します。

リスト A {4、5、9、10、1}

リスト B {21, 7, -4, 180}

したがって、ここでの唯一の一致は次のとおりです: {10, 1, 4, 9} <=> {21, 7, -4}

この種の問題に対する既存のアルゴリズムがあるかどうかは誰にもわかりませんか?

これまでのところ、私が持っている唯一の解決策は、すべての組み合わせを試す力ずくのアプローチですが、指数時間で実行され、時間がかかりすぎないように考慮する要素の数に厳しい制限を課す必要がありました。

私が考えることができる他の唯一の解決策は、両方のリストで階乗を実行し、そこで等値を探すことですが、それでもあまり効率的ではなく、リストが大きくなるにつれて指数関数的に長くかかります.

第一に、私はプログラマーではなく、プログラミングやアルゴリズムを学んだことがありません。実際には、ほとんど awk または ruby​​ で、いくつかの bash をプログラムする必要があります。

今日のタスクでは、プレーン テキスト ファイルに巨大なデータ セット (浮動小数点数) があり、1 つのレコード/行があり、セットのすべての数値の合計がありますが、数値の一部 ( 1 つ) は負ですが、ファイルには表示されません (要素が負の場合は符号がありません)。

しかし、私はそれ/それらを見つけなければなりません：最初に正しい合計を計算しました（ ですべての数字を追加してawk）、それらの符号は気にしませんでした。ここで、元の合計 (記号を考慮したもの) と新しい合計の差がわかりました。しかし、差分/2 のようにまったく同じ合計を持つデータセットのすべてのサブセットを見つける必要があります。

例えば：

これで、1+2+3+4+5 - ORIG SUM: 15-5=10 の差を計算できます。10/2 = 5 なので、合計が 5 になるすべてのサブセット、つまり [1,4]、[2,3]、[5] を見つける必要があります。

それを行う適切な方法はありますか？私は awk、ruby、シェル スクリプトを好みますが、python と perl の両方を使用できます (外部ライブラリをインストールする権利がないため、外部ライブラリを頻繁に使用する必要はありません)。

前もって感謝します。

問題は次のとおりです。

正の整数の集合 { a1 , a2 , a3 , ... , an } が与えられ、その中に同じ数が存在しない (a1 は一度しか存在しない、a2 は一度しか存在しない、...) 例: A = {12 , 5 、7、91}。問題: A の 2 つの素集合 A1 = { b1,b2,...,bm } と A2 = { c1,c2,...,ck} があり、b1+b2+...+bm = c1+ c2+...+ck ?

次の点に注意してください: A1 と A2 が A をカバーすることは必須ではないため、問題が自動的に部分和問題に還元されることはありません。例: A = {2,5,3,4,8,12} A1= {2,5} したがって、A1 の合計は 7 A2= {3,4} したがって、A2 の合計は 7記述されたプロパティなので、問題は解決されます。

どうすればこの問題を解決できますか? 可能なすべての (互いに素な) サブセットを見つけて、それらの合計を計算し、2 つの等しい合計を見つけるよりも良いことはできますか?

お時間をいただきありがとうございます。

C++ でループを作成して、6 つの乱数を取得し、それらを配列に格納しました。私がやりたいのは、数値「x」よりも大きい値が得られるまで配列の要素を合計することですが、必ずしもすべての要素を追加せずにこれを実行したいと考えています。目的は、合計が x の値になる最初の要素を見つけることです。

たとえば、配列は[1,2,3,4,5,6]、およびx = 6であるため、私が探しているのは要素[1,2,3]です。

私は標準ライブラリを見て、「valarray」の sum 関数を使用しようとしましたが、これはすべての要素の合計を与えるだけです。これをうまくコーディングする方法についてのアイデアは大歓迎です。

この投稿を投稿する理由は、未処理の請求書と照合して決済するのではなく、「支払い」がアカウントに転記される顧客の売掛金勘定を調整することを検討しているためです。だからここに私の問題があります：

特定の一連の数字 (請求金額) のサブセットと等しい単一の数字 (支払い) を用意します。簡単な例:

お支払い $10,002

請求書の値:

5001 2932 876 98 21 9923 2069 123 432 765

このセットから 5001、293​​2、および 2069 を引き出す方法が必要です。

プログラマーではないので、Excel スプレッドシート アプリケーションを作成するのが最も簡単です。アイデア？

サブセット和検索を実行するようにTI-83をプログラムしようとしています。したがって、長さNのリストが与えられた場合、与えられた長さLのすべてのリストを見つけたいと思います。その合計は、与えられた値Vになります。

これは、通常のサブセット和問題とは少し異なります。これは、すべての長さではなく、指定された長さのサブセットのみを検索しているためです。また、作業中のプログラムを呼び出すことができないため、再帰が必ずしも最初の選択肢ではありません。

ネストされたループを使用してタスクを簡単に実行できますが、Lの値が5より大きい場合は面倒になります。動的なソリューションを試していますが、どこにも到達していません。

実際、この時点で、私はリスト参照を正しく取得しようとしているだけなので、それが私が見ているものです。例を見てみましょう：

それで

長さ3のすべてのサブセットを探して、比較的短くして、L = 3（6c3 =合計20の出力）にします。

理想的には、検索されるリスト参照は次のとおりです。

明らかに次の方法で達成されます。

最初にNのデータを降順で並べ替えて、検索を短縮する条件を検索できるようにします。ループ内のA、B、Cの値をインクリメントすると、FORループを使用してさまざまな場所でデータを少し台無しにします。

また、より優れた動的ソリューションを探しています。私はウェブ上でいくつかの調査を行いましたが、そこにあるものを私の特定の状況に適応させることができないようです。

どんな助けでもいただければ幸いです。小説を書かないように簡潔にしようとしていますが、私が何をしようとしているのかを説明しています。必要に応じて詳細をお知らせします。

おそらくご存じのとおり、このSUBSET-SUM問題は、一連の整数のサブセットの合計が指定された整数になるかどうかを判断するものとして定義されています。(整数のグループの合計がゼロになるサブセット合計の別の定義がありますが、ここではこの定義を使用しましょう)

たとえば、合計すると((1,2,4,5),6)です。私たちはそれがtrue(2,4)6(2,4)"solution"

さらに、引数の合計((1,5,10),7)がfalse7

私の質問は、引数の数のセットが与えられた場合SUBSET-SUM、可能な解の数に多項式の上限があるかどうかです。最初の例では(2,4)とがあり(1,5)ました。

SUBSET-SUMNP完全であるため、ポリノメール時間で決定することはおそらく不可能であることがわかっています。ただし、私の質問は決定時間とは関係ありません。ソリューションのリストのサイズについて厳密に質問しています。

明らかに、引数の数の累乗セットのサイズが解リストのサイズの上限になる可能性がありますが、これは指数関数的に増加します。私の直感では、多項式の境界があるはずですが、これを証明することはできません。

これは宿題の質問のように聞こえるかもしれませんが、そうではないことを信じてください。私は CS 理論の特定の側面を独学しようとしていますが、これが私の考えが私を導いたところです。

正の整数のコレクションが与えられた場合、合計がしきい値を超える最小の合計である整数のサブセットが必要です。

それを解決するための汎用アルゴリズムのように見えるものを思いついたとき、サブセットサムの問題について読んでいました。

「set」は重複を含まないリストで、「sum」はサブセットを検索する合計です。"subsets" はコンス セルのリストで、"car" はサブセット リストで、"cdr" はそのサブセットの合計です。新しいサブセットは、要素を前面にコンスするだけで、古いサブセットから O(1) 時間で作成されます。

実行時の複雑さはわかりませんが、各要素の「合計」が大きくなると、「サブセット」のサイズが2倍になり、プラス1になるように見えるため、少なくとも2次のように見えます。

以前の印象では、NP完全問題は扱いにくい傾向があり、通常期待できる最善の方法はヒューリスティックであるという印象があったため、これを投稿していますが、CPUサイクルがあると仮定すると、これは汎用目的のソリューションのようです、常に正しい答えを教えてください。このような NP 完全問題を他にいくつ解くことができますか?