問題タブ [knapsack-problem]

与えられた数を構成するのに必要な最小数のコインを返すコードを書こうとしています。私のメソッドへの入力は、有効なコインの配列と、私が作成しようとしている数です。

ただし、これはほとんどの場合に機能しますが、次のように入力すると次のようになります。

答えは2でなければなりませんよね？しかし、それは印刷されます：

-2147483647

私は何を逃しましたか？

重みの合計が指定された重み W と正確に等しいセット内の重み付き要素のすべての可能な組み合わせを見つけたいと思います

{ 'A', 'B', 'C', 'D', 'E' }セットwhereweights = {'A':2, 'B':1, 'C':3, 'D':2, 'E':1}およびから k 個の要素を選択したいとしますW = 4。

次に、これは次のようになります。 ('A','B','E') ('A','D') ('B','C') ('B','D','E') ('C','E')

強引な方法は、指定されたセットのすべての順列を ( を使用してitertools.permutations) 見つけ、最初の k 個の要素を W の重み付き合計でスプライスすることだと認識しています。しかし、私はセットごとに少なくとも 20 個の要素を扱っています。高い。

ナップザックのバリアントを使用すると、重みのみ (値ではなく) が考慮され、重みの合計がW (劣っていない)に等しくなければならない場合に役立つと思います。

これをPythonで実装したいのですが、cs理論のヒントがあれば役立ちます。エレガンスにボーナスポイント！

次の0-1ナップサック問題は解決可能ですか？

• 「float」の正の値と
• 「フロート」ウェイト（正または負の場合があります）
• ナップザックの「フロート」容量>0

私は平均して10未満のアイテムを持っているので、力ずくの実装を使用することを考えています。しかし、もっと良い方法があるのではないかと思っていました。

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

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

例。 ベルト幅 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. 遺伝子群と粒子群 これらについては不明です。

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

サンプル出力:

注: "Turbo C" コンパイラでコンパイルすると、同じプログラムが同じ入力に対して正当な出力を生成します。

そのため、私はC標準に準拠していないと信じています。そうですか？

みたいな

最大重量 3

1番目と3番目を取ります。しかし、合計値を見つけることができません。1955+101。

私はナップサック0-1を使っています。とにかく、配列から 1955+101 を見つける方法はありますか

問題は、次の情報を使用して貪欲なアルゴリズムでナップザックの問題を追跡する方法です。

誰かがこれを理解するのを手伝ってくれたり、正しい方向に向けてくれたりしてくれたら幸いです。

私のコードでは、C を容量、N をアイテムの量、w[j] をアイテム j の重量、v[j] をアイテム j の値とすると、0- 1 ナップザックアルゴリズム? いくつかのデータセットでコードを試してみましたが、そのようです。私がこれを不思議に思っている理由は、私たちが教えられてきた 0-1 ナップザック アルゴリズムが 2 次元であるのに対し、これは 1 次元だからです。

これが 0-1 ナップザック アルゴリズムの私の実装です: (同じ変数を使用)

Dynamic Programming - Kapsack Problem (YouTube)を見ました。ただし、制約が予算、価格であり、整数ではなく倍精度であるという、わずかに異なる問題を解決しています。それで、どうすればそれを変更できるのだろうか？Double は、1,2,3 を持つことができる整数とは異なり、「連続的」です .... 0.0、0.1、0.2 を行うとは思いません ...?

更新 1

100 を掛けて double を int に変換することを考えました。お金は小数点以下 2 桁しかありません。しかし、それは値の範囲が非常に大きくなることを意味しますか?

更新 2

私が解決する必要がある問題は次のとおりです。

アイテムには、価格 (倍精度) と満足度 (整数) の値があります。制約として予算があり、満足度を最大化する必要があります。

YouTube 動画では、作者は int[numItems][possibleCapacity(weight)] のような 2 つの 2 次元配列を作成しました。ここでは、予算が整数ではなく倍精度であるため、できません

3次元ナップザック問題を解きたいです。

幅、高さ、長さ、値が異なる箱がいくつかあります。指定されたスペースがあり、最適な利益が得られるように、そのスペースにボックスを配置したいと考えています。ブルートフォースを使ってやりたいと思います。

私はJavaでプログラミングしています。私は再帰でそれをやろうとしたので：

しかし、各行に異なる空き x、y、z があるという問題が発生します。

誰かがそれを行う別の方法を見つけるのを手伝ってくれませんか?