問題タブ [knapsack-problem]

正規の CS 問題の良いリファレンスを知っている人はいますか?

「仕分け問題」、「ビン詰め問題」、「しつこいセールスマン問題」などを考えています。

編集：ウェブサイトを優先

固定サイズのブロックの束で構成された大きなファイルがあるとします。これらの各ブロックには、いくつかの可変サイズのレコードが含まれています。各レコードは 1 つのブロック内に完全に収まる必要があり、定義上、そのようなレコードは完全なブロックより大きくなることはありません。時間の経過とともに、レコードがこの「データベース」に出入りするにつれて、これらのブロックにレコードが追加されたり、ブロックから削除されたりします。

ある時点で、特に多くのレコードがデータベースに追加され、いくつかが削除された後、ブロックの多くが部分的にしか埋められない場合があります。

このデータベース内のレコードをシャッフルして、部分的に満たされたブロックをより適切に埋めることにより、ファイルの末尾にある不要なブロックを圧縮するための適切なアルゴリズムは何ですか?

アルゴリズムの要件:

• 圧縮は、元のファイルの代わりに発生する必要があり、その開始サイズからせいぜい数ブロック分以上ファイルを一時的に拡張する必要はありません。
• アルゴリズムは、すでにほとんどがいっぱいになっているブロックを不必要に妨害してはなりません
• ブロック全体を一度にファイルから読み書きする必要があり、書き込み操作は比較的高価であると想定する必要があります
• レコードをあるブロックから別のブロックに移動する場合、操作が中断された場合に「失敗した」圧縮の結果としてレコードが失われないように、開始位置から削除する前に新しい場所に追加する必要があります。(このようなレコードの一時的な重複は、回復時に検出できると仮定します)。
• この操作に使用できるメモリは、全体のファイル サイズの非常に小さな割合である、おそらく数ブロック程度です。
• レコードが 10 バイトから 1K バイトのオーダーで、平均サイズがおそらく 100 バイトであると想定します。固定サイズのブロックは 4K または 8K のオーダーであり、ファイルは 1000 のブロックのオーダーです。

簡単な概要

ナップザック問題について調べてみました

http://en.wikipedia.org/wiki/Knapsack_problem

それが私のプロジェクトに必要なものであることはわかっていますが、プロジェクトの複雑な部分は、メインの袋の中に複数の袋が必要になることです。

すべての「バッグ」を収納できる大きなナップザックは、x 個の「バッグ」しか持ち運べません (例として 9 個としましょう)。各バッグには異なる値があります。

• 重さ
• 料金
• サイズ
• 容量

など、これらの値はすべて整数です。0から100までと仮定しましょう。

内側のバッグにもタイプが割り当てられ、プログラム入力には同じタイプの複数が与えられますが、外側のバッグ内にはそのタイプの 1 つしか存在できません。

メイン バッグが保持できる最大重量を割り当てる必要があり、小さいバッグの他のすべてのプロパティは重み付けされた値でグループ化する必要があります。

例

アウターバッグ:

• 小さめのバッグなら9個収納可能
• 体重が98以下 [ギブオアテイク5]
• 各タイプを 1 つ保持する必要があり、一度に各タイプを 1 つだけ保持できます。

インナーバッグ:

• コスト、100% で加重
• サイズ、加重 67%
• 容量、加重 44%

プログラムには複数のバッグの入力が与えられ、小さなバッグの組み合わせを大きなバッグに入れる必要があります。入力に応じて複数のソリューションがあり、プログラムは最適なソリューションを出力します。

私がこれにアプローチするための最良の方法は何だと思いますか。

JavaまたはC#でプログラミングします。PHP でプログラムしたいのですが、Web サーバーにとってアルゴリズムが非常に非効率的ではないかと心配しています。

あなたが与えることができる助けをありがとう

-ザック

私はVB.NETを使用していて、いくつかのアルゴリズムや疑似コード、または次のことを実行できるVB.NETコードを考え出そうとしています（うまくいけば、これをうまく説明できます）。

Cob1とCob2の2つのコレクションオブジェクトがあります。これらのコレクションオブジェクトは、ICobと呼ばれるインターフェイスを実装するオブジェクトを格納します。ICobには3つのプロパティがあります。ブール値のIsSelectedプロパティ、TimeSpanを返すLengthと呼ばれるプロパティ、および短整数であるRatingプロパティ。

これで、Cob1のコレクションには約100個のオブジェクトが保存され、Cob2は空のコレクションになりました。私がやりたいのは、Cob1からオブジェクトを選択し、それらをCob2にコピーすることです。ただし、オブジェクトを選択するときは、次のルールに従う必要があります。

1. タイムスパンを指定できるようにしたいのですが、（Lengthプロパティに基づいて）指定したタイムスパンに収まるように十分な数のオブジェクトを選択する必要があります。したがって、たとえば、関数に10分のタイムスパンを渡す場合、10分のウィンドウ全体を埋めるのに十分なオブジェクトを選択するか、可能な限りいっぱいに近づける必要があります。

2. オブジェクトを2回選択しないでください。

3. （Ratingプロパティを介して）より高い評価を持つオブジェクトは、他のオブジェクトよりも選択される可能性が高くなります。

4. 評価に関係なく、過去30分間に選択されたオブジェクトを再度選択することはできません（各オブジェクトが最終的に少なくとも1回選択されるようにするため）。

誰かがこれを達成する方法についていくつかのヒントを教えてもらえますか？ヒントは、メンタルプロセス、VB.NETサンプルコード、擬似コード、または私に役立つ可能性のあるその他のものの形をとることができます。

ありがとう

編集：

実生活で何をしようとしているのかを明らかにしておけば、みんなに役立つかもしれません。

私はラジオ局用のソフトウェアを書いています。これは、コンピューター化されたプログラムマネージャーのように、再生する音楽と広告を自動的に選択します。

長さはサウンドバイト（曲または広告）の長さを表し、評価はそれだけです。曲が人気のある場合、それはより多くの放送時間を取得します。広告主がより多くのお金を払うならば、それはまたより多くの放送時間を得る。

したがって、私のプログラムでは、20分ほど再生される曲を選択してから、約5分程度再生する広告をいくつか選択する必要があります。

うまくいけば、これは少し役立つでしょう。

皆様からのご意見ありがとうございました！

アラン

番号のリストがあります。
このリストは、合計の差が最小限になるように、同じサイズの 2 つのリストに分割されます。合計を印刷する必要があります。

場合によっては、次のコード アルゴリズムにエラーがありますか?

これを最適化および/またはPython化するにはどうすればよいですか?

質問はhttp://www.codechef.com/problems/TEAMSEL/からです

合計 540000 の数字のリストがあります。このリストを 3 つのリストに並べ替えて、それぞれ合計 180000 にしたいと思います。これを行うための最も効率的なプログラミング方法は何ですか?ライン？

複数の制約がある場合（たとえば、各アイテムの体積と重量が関連していない、体積制限と重量制限の両方）、多重制約ナップサック問題、多次元ナップサック問題、またはmが得られます。 -次元ナップサック問題。

これを最も最適化された方法でコーディングするにはどうすればよいですか？さて、ブルートフォース再帰ソリューションを開発することができます。分枝限定法かもしれませんが、ある種のメモ化を行うか、うまく行かないと大量のメモリを消費する動的計画法を使用するまでは、ほとんどの場合、本質的に指数関数的です。

私が直面している問題はこれです

両方に上限があるため、一般的なKnapSack（Capacity、i）の代わりにknapsack関数KnapSack（Capacity、Value、i）を使用しています。誰かがこれで私を導くことができますか？または、適度に大きいnのこれらの問題を解決するための適切なリソースを提供します

または、このNPは完全ですか？

ありがとう

シーケンシャル バージョンよりもパフォーマンスを向上させるために、Java でマルチスレッド アプリケーションを作成しています。これは、0/1 ナップザック問題に対する動的計画法ソリューションの並列バージョンです。異なるパーティションに Ubuntu と Windows 7 Professional の両方を搭載した Intel Core 2 Duo を使用しています。私はUbuntuで実行しています。

私の問題は、並列バージョンが実際には順次バージョンよりも時間がかかることです。これは、スレッドがすべて同じカーネルスレッドにマップされているか、同じコアに割り当てられているためだと考えています。各 Java スレッドが個別のコアにマップされるようにする方法はありますか?

この問題に関する他の投稿を読みましたが、何も役に立たないようです。

以下は、(Thread を拡張する) KnapsackThread クラスの main() とすべての run() の終わりです。スライスとエクストラを使用して myLowBound と myHiBound を計算する方法は、各スレッドが dynProgMatrix のドメインで重複しないようにすることに注意してください。したがって、競合状態は発生しません。

アップデート：

ブルート フォースを使用する別のバージョンのナップザックを作成しました。このバージョンでは、1 つのスレッドの実行の最後に bestSoFar 変数を更新するだけでよいため、同期はほとんどありません。したがって、各スレッドは、最後の小さなクリティカル セクションを除いて、ほぼ完全に並行して実行する必要があります。

これをシーケンシャルブルートフォースと比較して実行しましたが、それでも時間がかかります。スレッドが同じコアまたは同じネイティブ スレッドにマップされているため、スレッドが順次実行されているという以外の説明はありません。

誰か洞察力がありますか？

knapsack問題は(またはそのタイプで、値がなく、正の重みのみ)よりも単純です。この問題は、数が他の数の組み合わせになり得るかどうかをチェックすることから成ります。関数はtrueまたはを返す必要がありfalseます。

例えば、

112 と、{ 17, 100, 101 }を返す必要があるリストfalse、469同じリストを返す必要がある、返す必要があるtrue、返す必要がある、など...35false119true

編集：ナップザックよりもサブセットサムの問題の方が正確です。

複数のナップザック問題を効果的に解決する擬似コードを探しています(最適化ステートメントはページの途中にあります)。この問題は NP Complete であると思いますので、ソリューションが最適である必要はなく、かなり効率的で簡単に実装できれば良いと思います。

問題はこれです：

• 多くの作業項目があり、それぞれが完了するまでにかかる時間が異なります (ただし固定されており、既知の時間)。
• これらの作業項目をグループに分割して、(理想的には) グループの数を最小にし、作業項目の各グループが所定の合計しきい値 (たとえば 1 時間) を超えないようにする必要があります。

私はしきい値について柔軟です。厳密に適用する必要はありませんが、近い値にする必要があります。私のアイデアは、各ビンがしきい値の 90%、80%、70% などを表すビンに作業項目を割り当てることでした。次に、90% かかるアイテムと 10% かかるアイテムを一致させることができます。

より良いアイデアはありますか？