問題タブ [knapsack-problem]

実際には、確率のあるオブジェクトのセットがあり、それらが独立していると仮定して、それらがすべて真である可能性が高い順に、つまり、次の降順で、それらの可能な各グループを調べたいと思います。サブセットの要素の積-または確率が同じ場合は長さの順に（（1、0.5）が（0.5）の後に来るように）。

例：[ 1, 0.5, 0.1 ]必要な場合[ (), (1), (0.5), (1, 0.5), (0.1), (1, 0.1), (0.5, 0.1), (1, 0.5, 0.1) ]

本質的に、これは、要素のセットのべき集合を順番に反復したいことを意味し、これをかなり簡単に生成し、並べ替えて、実行することができます。ただし、べき集合はかなり速く大きくなります。通常、最初のサブセットの1つが必要になると思います。何千ものサブセットのリストを生成して並べ替えてから、3番目のサブセットを超えないようにします。これは、Pythonジェネレーターが1日を節約できる場所です。

問題のより正式な仕様sorted(powerset(input), key = lambda l : reduce (lambda (p, n), e: (p * e, n-1), l, (1, 0)), reverse=True)として、ジェネレーターとして、またはリスト全体の作成と並べ替えを回避できるその他の方法を検討する必要があります。

これは、サブセット製品の問題とともに、ナップサック問題に関連していると合理的に確信していますが、機能する優れたアルゴリズムを取得するのに本当に苦労しています。助けていただければ幸いです:-)。最悪の場合（最後まで繰り返す）で全体を構築+並べ替えるよりも遅くなることは問題ではありません。必要なのは、はるかに優れた最良の場合（たとえば、最初の10％以内）のパフォーマンスだけです。

Haskell で0-1 ナップサック問題をコード化しました。これまでに達成された怠惰さと一般性のレベルについて、私はかなり誇りに思っています。

まず、遅延 2 次元行列を作成して処理するための関数を提供します。

次に、特定のナップザックの問題について特定の表を作成します

最後に、テーブルを表示するためのヘルパー関数をいくつか追加します。

ここまではかなり簡単でした。しかし、私はそれをさらに一歩進めたいと思っています。

テーブルのデータ構造を改善したい。理想的には、

• ボックス化されていない (不変) [編集] 気にしないで
• 怠惰
• 無制限
• O(1)構築する時間
• O(1)特定のエントリを検索するための時間の複雑さ
  (より現実的には、最悪のO(log n)場合、ni*jは行 i、列 j のエントリを検索するためのもの)

ソリューションがこれらの理想を満たしている理由/方法を説明できればボーナス ポイントです。

knapsackTableをさらに一般化し、それが効率的であることを証明できれば、ボーナス ポイントも得られます。

データ構造を改善するには、次の目標を満たすようにしてください。

• 最大重みが 10 であるソリューションを求める場合 (私の現在のコードではindexTable knapsackTable 5 10、5 は項目 1 ～ 5 を含むことを意味します)、必要最小限の作業のみを実行する必要があります。理想的には、これはO(i*j)、テーブルの各行の背骨を必要な列の長さに強制する作業がないことを意味します。DP がテーブル全体を評価することを意味すると考える場合、これは「真の」DP ではないと言えます。
• テーブル全体を印刷するように要求した場合 (のようなものprintTable knapsackTable 5 10)、各エントリの値は一度だけ計算する必要があります。特定のセルの値は、他のセルの値に依存する必要があります (DP スタイル: 考え方として、同じ部分問題を 2 回再計算しないでください)。

アイデア:

• Data.Array境界 :(
• UArray厳密 :(
• メモ化技術（HaskellのDPに関するSOの質問）これはうまくいくかもしれません

私の述べた理想にある程度の妥協をする回答は、有益である限り、（とにかく私によって）支持されます。妥協が最も少ない答えは、おそらく「受け入れられる」ものになるでしょう。

したがって、練習用の質問では、0/1ナップサック問題のバリエーションである動的計画法アルゴリズムを設計することになっています...基本的に、各アイテムは4つの異なるソースから取得され、そのアイテムは1つのソースからのみ取得できます。 。

つまり、

のために、あなたが置くn = 10ことを選択した場合、それはあなたが選択しないことを意味します...i = 166, 26 or 36

この問題を解決し、漸化式を考案するのを手伝ってもらえますか？

ウェイトとウェイトカウントに指定されたナップサック容量でナップサック問題が発生しました。

ナップザックの容量がC、必要なウェイト数がN、ウェイトのリストがある場合に、ウェイトをナップザックにパックするアルゴリズムが必要です。重みの並べ替えは重要ではありません。アルゴリズムが再帰的であることが最善です。

例：
ナップザックの魔女は3つのウェイトしか保持できず、10のウェイトが必要で、9、8、7、2、1のウェイトがあります。正しい（そして唯一の）答えは7、2、1です。

誰かが擬似コードを書くのが最善ですが、一般的なプログラミング言語のいずれかであれば問題ありません。

PSどんなヒントもありがたいです:)

[編集]正確にCに重みを付ける正確にN個の重みカウントで答えを与えるアルゴリズムが必要です。

この疑似コードからJavaでサブセットの合計問題を実装する方法を知っている人はいますか?

これは本当に私を困惑させているので、コメントを追加できれば素晴らしいでしょう!!!

だから私は授業のためにナップザック問題を解かなければなりません。これまでのところ、私は次のことを考え出しました。私のコンパレータは、(対応する (value,work) タプルを見て) 2 つのサブジェクトのどちらがより良い選択肢になるかを決定する関数です。

maxWork 未満の仕事で可能な主題を反復することに決め、任意の時点でどの主題が最良の選択肢であるかを見つけるために、最新の主題をまだ使用していない他のすべての主題と比較しました。

問題は、なぜこれが間違っているのか分からないことです。エラーが発生し、コードのどこが間違っているのかわかりません (print ステートメントを投入した後でも)。助けていただければ幸いです、ありがとう！

誰かがこの問題の解決策を、選択したプログラミング言語 (できれば Python ですが、何でもいいと思います) で考え出すことができますか?

さまざまなトラック長グループがあります。たとえば、次のようにします。

およびソース トラック自体:

そして、上記の長さのグループに属するトラックを実用的に見つける必要があります。例のように、最初の 2 つのトラックは、合計の長さがグループの長さに等しいため、最初のグループに属します。

前もって感謝します

編集：それは私の宿題ではありませんが、それは私が抱えている問題であり、私はプログラマーではありません。itertools を見てみましょう、ありがとう

edit2: ご提案ありがとうございます。私はPythonスクリプトを作成しましたが、問題なく高速に動作する場合。最適化されていないことは確かですが、スケルトンは次のとおりです。

これを手動で追跡すると、私の人生よりも時間がかかるので、これを解決してよかったです。

遺伝的アルゴリズムを使用したナップザック問題については質問していません。初期化 私はこの種の染色体 [1] = [重み] [利益] を使用します。これは、染色体評価重み x 利益に関する彼の式 KP からです。ルーレットホイールの選択を使用してエントリした後ではありません。p (a) = 0.04761/0.19761 = 0.24092; p (b) = 0.1/0.19761 = 0.50604; p (c) = 0.025/0.19761 = 0.12651。次に、乱数を生成する setelag は、乱数ができるようになった後、どのようにクロスオーバーしますか?

説明してください、助けてください

私の問題は次のとおりです-

以下のようないくつかの数字があります-

したがって、次の数値を入力として指定すると、出力は次のようになります-

[出力は、与えられた数値の合計であり、入力よりも大きい]

結果を得るために、すべての組み合わせ（つまり、ブルートフォース）を試したいだけではありません。上記の状況で可能な効率的なアルゴリズムはありますか？

ありがとう。

問題

このようなデータのハッシュがあります。

GROUP_A には 22 個のアカウントがあり、440 GB のデータを使用しています...など。これらのグループは数百あります。多くのアカウントを持っているがストレージをほとんど使用していない人もいれば、少数のユーザーしか持たず大量のストレージを使用している人もいれば、平均的な人もいます。

これらのアカウントのグループを入れたい X 個のバケット (サーバー) があり、バケットごとにほぼ同じ数のアカウントがあり、各バケットにもほぼ同じ量のデータが含まれている必要があります。グループの数は重要ではないため、バケットに 500 GB のデータを使用する 1000 アカウントの 1 グループがあり、次のバケットに 450 GB のデータを使用する 97 アカウントの 10 グループ (合計 970) がある場合...私はそれを良いと呼びます。

これまでのところ、これを行うアルゴリズムは思いつきませんでした。心の中では、こんなことを考えているのではないでしょうか？

私はまだこれを理解するためのより良い方法があると思いますが、それは私には来ていません. 誰かが何か考えを持っているなら、私は提案を受け入れます。

マット

解決策 1.1 - ブルート フォース アップデート

さて....これが最初の試みの更新です。これはまだ「ナップザック問題」の解決策ではありません。アカウントがバケット全体でバランスを取るように、データをブルートフォースするだけです。今回は、いくつかのロジックを追加して、バケットのアカウントとデータの完全な割合が高い場合に、アカウントの数に基づいて最適な (データによる) 最大のグループを見つけられるようにしました。最初の試みと比較して、データの分散が大幅に改善されました (最初の試みを見たい場合は、編集履歴を参照してください)。

現在、各バケットを順番にロードし、バケット 1 を満たし、次にバケット 2 を満たします。コードを変更して、それらを同時に (またはほぼ同時に) 満たすようにすれば、データ バランスが改善されると思います。

たとえば、1 番目の部門をバケット 1 に、2 番目の部門をバケット 2 に、というように...すべてのバケットが 1 つの部門になるまで...その後、再びバケット 1 から始めます。

...そして結果...

(379 * 6 <> 2279) MAX_ACCTS がバケットの数で割り切れない場合を考慮する方法を理解する必要があります。AVG_ACCTS 値に 1% のパッドを追加してみました。この場合、平均は 383 になると思いますが、すべてのバケットが 383 アカウントを持っていると言っています...これは真実ではありません。バケット内のアカウント数が MAX_ACCTS を超えています。まだ見つけていないコードのどこかに間違いがあります。