問題タブ [subset-sum]

この特定のケース（C＃またはelseアルゴリズム）のサブセット合計問題の解決策を探しています：

1) セットには約 1,000 の数字があります (数千になる可能性があります)。

2) 総額は数十億に達する

3) 数値は通貨値であるため、小数点以下 2 桁の精度を持ちます (例: 2,345.17)

4) セット内の数値は、正と負の両方になる可能性があります (したがって、正味合計を扱う)

次に、この検索を (同じ数のセットで) 繰り返す必要がありますが、合計は最大 1,000 回までです。そして最後に、プロセス全体が 1,000 回実行されます。つまり、1,000,000 回の実行を見ています。目標は、2分でそれを達成することです。つまり、各実行にかかる時間は 0.12 ミリ秒以内です。

これは実現可能ですか？

-クリップ

この問題を解決する方法を教えてください。

k 個の要素を含む集合 S が与えられます。

ここで、集合 S を x 個のサブセットに分割して、各サブセットの要素数の差が 1 以下になり、各サブセットの合計が互いにできるだけ近くなるようにする必要があります。

例 1: {10, 20, 90, 200, 100} は 2 つのサブセットに分割する必要があります

解決策:{10,200}{20,90,100}

合計は 210 と 210

例 2: {1、1、2、1、1、1、1、1、1、6}

解決策:{1,1,1,1,6}{1,2,1,1,1}

合計は 10 と 6 です。

重複の可能性:
等しい k サブセット アルゴリズム

数値のセットがあるとします。数値が均等に分散されるように、数値を k 個のサブセットに分割したいとします。均等に分布するとは、サブセット内の値の合計が他のサブセットの他の合計に最も近いことを意味します。この問題に対する DP ソリューションを実装できますか??

提案してください！

次の問題:

曲を含むMySQLデータベースがあります。データベースの構造は次のとおりです。

ユーザーは特定の時間を php フォームに入力できる必要があり、php 関数は指定された時間 ±X 分になる曲のすべての可能な組み合わせのリストをユーザーに提供する必要があります。

したがって、ユーザーが 1 時間±5 分の音楽を聴きたい場合、フォームに 60 分と 5 分のしきい値を入力し、合計で 55 ～ 65 分になるすべての可能な曲セットを受け取ります。重複を出力するべきではありません。

私はすでにこの問題へのいくつかのアプローチを見つけましたが、それらは曲名などではなく、Xになるまでの期間のみを返しました。したがって、私の問題は、これを解決して追加する曲のIDを返す方法ですするか、対応する曲名のリストを印刷します。

これは私が見つけた最良の答えの 1 つに思えますが、データベースに適応させることができません。

私はこのコードを持っています...それは私が必要とすることをほぼ正確に行います。定義済みの int 配列から、合計がターゲット int になる 2 つの int を検索します。ただし、セル内に値を配置するのではなく、ベクトルに値を配置する場合、すべての値が一緒に配置されます。つまり、int array[50,40,30,20,10] とターゲット 50 の場合、[[50][40,10][30,20]...etc.] を返すのではなく、[[50,40] を出力します。 ,10,30,20...など]] どうすれば修正できますか?

subsetSum のアルゴリズムを記述しようとしています... 指定されたベクトルのすべての可能なサブセットを見つけてから、どれがターゲット値になるかを見つけます。ただし、nullpointerexceptions とその他のいくつかのエラーが発生し続けます。誰かが私を助けることができますか？私は窮地に立たされており、脳はほとんど機能していません。とても有難い。ありがとう。

78 行目は、subsetSum メソッドの最初の for ループの行です。

これが多項式時間で実行できるかどうかさえわかりません。

問題：

実数の 2 つの配列が与えられると、

および数値、 のサブセットをk見つけます。このサブセットには、が最大化されているような要素が正確に含まれています。ここで、 .A'A (A' = (a[i(1)], a[i(2)], ..., a[i(k)]))k(sum a[i(j)])/(sum b[i(j)])
j = 1, 2, ..., k

たとえばk == 3、 と{a[1], a[5], a[7]}が結果の場合、

他のどの組み合わせよりも大きくする必要があります。どんな手掛かり？

この実際的な問題についてコメントをいただければ幸いです。

簡単な説明。 特定のベルト幅を構成するために使用できる可変数のリンクがあります。問題は、各リンクの数です。選択基準: より長いアイテムを使用することをお勧めします。

例。 ベルト幅 W = 1024.0 を作成したいとします。モデルの 1 つは、次のリンクの長さを持っています: L = [34.0, 65.0, 96.0, 126.0]

問題は、幅を作るために各リンクの数です。

ここに私が試したいくつかのアプローチがあります。

1. 貪欲 (条件を満たすために最長の最初のものを選択) c = [0,0,0,8] ここで、c は各項目のカウントです。これは 16.0 のギャップを残し、最小のアイテムの 1 つでも収まりません。貪欲は簡単ですが、良くありません。

2.選択ループ 簡単すぎず、難しい問題だと思います。私は多くの戦略を試しました。小さなアイテムを詰めてから、次のサイズに合わせて順番に削除します。

3. ナップザック方式 これはアイテム数が決まっているためあまり適切ではありません。

4. 部分和問題 これは Knapsack のサブクラスですが、私はそれを機能させることができませんでした。

5. Bin Packing problem 似ているように聞こえますが、私の問題には当てはまりませんでした。

6. ブルート フォース (ランダム選択) 奇妙なことに、これは多くの正確な一致を見つけます。カウントの単純な多項式を評価として使用します。rating = n[0] + n[1]* 2 + n[2] *3 + n[4]**4 + ... ブルート フォースからの解の 1 つは [4, 0, 4, 4] です。正確には 1024 です。問題は、この方法では異なる選択が行われることが多いため、理想的ではないことです。

7. 網羅的検索 選択肢が多すぎるため実用的ではありません。

8. シミュレーテッド アニーリング ブルート フォースの成功からすると、これは良い代替手段のように見えます。誰かが簡単な例を教えてくれませんか (別の巡回セールスマンはやめてください)。

9. 遺伝子群と粒子群 これらについては不明です。

今、私は立ち往生してイライラしています。この問題に使用できる直接アルゴリズムはありますか?

これは部分和問題の解決策です。バックトラッキングを使用しています。私はそれについて2時間以上考えていましたが、理解できません。

編集:私が理解したことに基づいて、コードにいくつかのコメントを追加しました。私が間違っている場合は修正してください。

注: これは実用的なソリューションです。g++ でコンパイルすると動作します。これが不快に思われる場合は申し訳ありませんが、コードからあまり理解できなかったため、多くの説明をすることはできません.

tardos のアルゴリズム設計書から NP 完全性について読んでいます。サブセット和が NP 完全であることを証明するセクションでは、次のように書かれてい
ます。サブセット和用に開発されたアルゴリズムの実行時間は O(nW) です。それぞれが 100 ビット長の 100 個の数値のインスタンスが与えられた場合、入力は 100 * 100 = 10000 桁にすぎませんが、W はおよそ 2^100 です。
この主張が理解できません。なぜ W 2^100 なのですか? この問題に対する base の影響は何ですか? つまり、それを別の base x に変更すると、W は x^100 になりますか? 単項ベースに変更するとどうなるでしょうか?
ありがとう。