問題タブ [knapsack-problem]

現在、Python 3.2 でナップザックの問題をコーディングしようとしています。これをマトリックスで動的に実行しようとしています。私が使用しようとしているアルゴリズムは次のとおりです

以下のコードを実行すると、重みをリストに挿入しようとすることがわかります。これは再帰を使用しているため、問題を見つけるのに苦労しています。また、「+」を使用してリストに整数を追加できませんというエラーが表示されます。最初の行と最初の列がすべて 0 で始まるようにマトリックスを初期化しました。それ以外はすべて -1 に初期化されています。どんな助けでも大歓迎です。

これは、動的計画法を必要とする典型的なナップザックの問題であり、項目の供給に制約はありません。私は自分のクラスでこれに取り組んでおり、アルゴリズムを何時間もいじってみましたが、まだそこに到達していません.

このメソッドは、アイテムの重量と値をそれぞれ含む W と V の並べ替えられた配列と、最大重量を表す整数 T を取ることになっています。私の出力では、T = 21 まではすべて機能しますが、その後は貪欲なアルゴリズムのように機能しているように見えますが、これは私が望んでいたものとはまったく異なります。ヒントをいただければ幸いです。

01MKP の ACO を実装しようとしています。私の入力値は OR-Library mknap1.txt からのものです。私のアルゴリズムによると、最初にアイテムをランダムに選択します。次に、構築グラフの他のすべての項目の確率を計算します。確率方程式は、フェレモン レベルとヒューリスティック情報に依存します。

私の pheremon マトリックスのセルは、初期値 (0.2) で定数値を持っています。このため、次のアイテムを見つけようとすると、フェレモン マトリックスが 0.2 のために無効になります。したがって、私の確率関数は、ヒューリスティック情報をチェックして、次に進むアイテムを決定します。ご存知のように、発見的情報方程式は

(Ravg はリソース制約の平均です)。このため、私の問題です。関数は、最大の利益値を持つアイテムを選択します。(最初の繰り返しで、私のアルゴリズムが 600 の利益を持つアイテムをランダムに選択したとしましょう。次に、2 回目の繰り返しで、2400 の利益値を選択します。しかし、OR-Library では、2400 の利益値を持つアイテムがリソース違反を引き起こします。 2番目に選ばれたのは、利益が2400のアイテムです。

私のアルゴリズムに何か問題がありますか？ACOについて何か知っている人が私を助けてくれることを願っています. 前もって感謝します。

入力値:

私のアルゴリズム:

プロジェクトに取り組んでいると、この問題に遭遇しました。ここでは、問題の実際の領域外の用語で言い換えます (花火と形状の口径について話すことはできると思いますが、理解がさらに複雑になります)。それを解決するための（おそらくおおよその）アルゴリズムを探しています。

さまざまなサイズのn 個のコンテナーと、さまざまなサイズの職業とさまざまな色の m個のオブジェクトがあります (オブジェクトは多色になる可能性があるため、オブジェクトの色は本当にセットです)。

私の目的は、コンテナーごとにさまざまな色が最小限に抑えられるように、すべてのオブジェクトをコンテナーに収めることです (それが可能であることは既にわかっています)。「色の種類が最小限に抑えられている」とは、コンテナごとの異なる色の数の合計が最小限であることを意味します。

例。サイズ 2 の 2 つのコンテナと、{red}、{red, green}、{blue}、{blue, green} の色を持つ 4 つのオブジェクトがあり、それぞれのサイズは 1 です。最適なソリューションは [{red} 、{赤、緑}]、[{青}、{青、緑}]、合計の種類は 2+2=4 です。悪い解決策は [{red}, {blue}], [{red, green}, {blue, green}] で、合計の種類は 2+3=5 です。

私の推測では、ナップザックの問題よりも難しいように聞こえるので、この問題は NP 困難であると思います。オブジェクトの値は負の値に変換され、さらに同じコンテナー内の他のオブジェクトに依存します。しかし、おおよその解決策を得るために問題に取り組む方法については、私には良い考えがありません。とにかくそれは大歓迎です。

JavaでMCKPソルバーを必死に探しています。私はこのようなオークションを解決するためにそれが必要です：3人の入札者、すべての入札者は同一のオブジェクトのバンドルに対して一連のオファーを行います。販売するアイテムが10個あり、1、2、3、4などのオブジェクトを提供できるとします。

明らかに、入札者ごとに1つのオファーのみを受け入れることができます。

したがって、これは明らかにMCKPです。

ありがとう、マット

宿題として、Javaで作成する次のプログラムがあります。

本棚には、K 人の作家が手でコピーしなければならない N 本のスタックがあります。各本には、Ai が本である Ui ページがあります。

各作家にスタックから連続した本を提供する必要があり、本のページを分割することはできません。

作家に本を与えるが、作家がコピーするページの最大数を最小限に抑えるプログラムを作成します。

入力として、ユーザーは数値の文字列を指定します。最初の数値は本の数 N、2 番目の数値は作家の数 K、残りの数値は各書籍のページ数です。

出力として、プログラムはライターがコピーする最大ページ数をユーザーに出力します。

例：

入力: 15 6 30 40 10 40 50 20 30 40 10 70 10 50 30 50 10
出力: 90

この例では、最初のライターは book1 = 30 と book2 = 40 を取得できますが、たとえば book1 = 30 と book3 = 10 を取得することはできません。つまり、スタックの一番上からのみ書籍を取り混ぜずに取得します。

これが私の実装です：

私がしていることは、リストの長さが作家の数と等しくなるまで、最小限の本のペアをマージするたびにですが、うまくいきません。この例では、90 ではなく 100 を出力します。

ナップザックのような問題に対する動的プログラミングの解決策と残忍な解決策について聞いたことがありますが、私の大学では動的プログラミングについてまだ教えていません。

私の解決策はうまくいくと確信していましたが、何らかの理由でうまくいきませんでした。これまたは私が間違っていた別の解決策のヒントを教えていただければ幸いです。

DP ソリューションまたは残忍なソリューションのいずれかを指摘することができますが、DP ソリューションを指摘する場合は、DP の実装についてほとんど知らないことに注意してください。

EDIT：私はすでにナップザックのような問題のいくつかを見てきましたが、私が理解できたこのバリエーションと非DPソリューションを持つものを見つけることができませんでした

動的計画法を使用して、合計が正の整数 K に最も近いが等しくない配列内の正の整数のリストを見つけるにはどうすればよいでしょうか?

私はこれについて考えて少し立ち往生しています。

最適化の問題があります。20個の部品が入った商品のことです（製作順は問いません）。20 個すべての部品を製造できる同様の機械が 3 台あります。

20 パーツを数分で表現しました (つまり、最初のパーツを作成するのに 3 分、2 番目のパーツを作成するのに 75 分かかります)。

したがって、1 つの製品を製造するには 730 分かかります。

3 台の機械に良品を割り付けることで、1 台の製品の生産量を最小化することを目的としています。

したがって、実際には 243.333 分 (730/3) に近づける必要があります。

可能性の量は巨大です 3^20

さまざまな最適解があると思います。私はRがそれらすべてを私にくれることを望みます。マシン 1 2 と 3 を必要とする合計時間を知る必要があるだけでなく、マシン 1、マシン 2、およびマシン 3 にどのアイテムを渡すかを知る必要もあります。

または、長すぎる場合は、できるだけ合理的な繰り返しのないサンプルを選択したいと思います...

R 言語で問題を解決できますか?

各数値にいくつかのコストが付加された数値のセットがNあり、問題は、可能なすべての数値のセットをリストとして選択して、それらの積が特定の数値未満になりM、コストの合計に従ってソートされることです。

例:- 数値のセットは

製品は、、、未満でなければなりませんProd <= 1000。

可能な解決策は次のとおりです:-

したがって、リストは になり{Solution2, Solution1}ます。

PS :-

1. これは宿題の問題ではなく、面接で聞かれました。私はアルゴリズムだけを尋ねられました。私が言えることは、ナップザックの問題に似ているように見えるということだけでした。
2. 問題を適切に説明できない場合は、ご容赦ください。

ナップサック問題のどのアルゴリズムがO（2 ^ n * n）の複雑さを持っていますか？

ナップサック問題の解決策を実装するように依頼されました。

私はプログラミングには精通していますが、漸近表記には精通していません。

どのアルゴリズムがO（2 ^ n * n）の複雑さを持っているかについて誰かが私にアドバイスできますか？