3

N枚の金貨とM枚の銀貨を持っています。それぞれコストのある k 個のアイテム、A 金貨と B 銀貨があり、A または B がゼロになることもあります。

最大数のアイテムを購入するアルゴリズムは何ですか?

4

3 に答える 3

4

これはナップザック問題ですか？

あなたが説明した問題は、ナップザックの問題ではありません。ここでは、合計コストではなく、アイテムの数のみを最大化します。ナップザックの問題では、代わりに、サックの容量を考慮しながら総コストを最大化することに関心があります。つまり、袋に収まる最も価値のあるアイテムを手に入れたいということです。それらの数はあまり気にしませんが、それらが最も価値のあるものであるということだけです!

以下では、問題の 2 つのバリエーションについて説明します。

  1. 単一通貨-- 金貨と銀貨は相互交換可能
  2. 複数の直交通貨-- 金貨は銀貨に変換できません。

単一通貨バリアント

N 枚の金貨と M 枚の銀貨しか使用できないと仮定すると、次のアルゴリズムが機能します。

1. Sort the items by cost, from cheapest to the most expensive.
2. totalCost = 0; i = 1
3. while totalCost <= goldToCost(N) + silverToCost(M) + item[i].cost
4.    totalCost = totalCost + items[i].cost
5.    i++
6. endWhile
7. return i

このアルゴリズムは、ソートのためにO(nlogn)時間しかかかりません。

多通貨バリアント

上記の解決策は、2 つの通貨を相互に変換できることを前提としています。問題の別のバリエーションには、2 つの通貨が互いに変換できない直交通貨が含まれます。この場合、すべてのコストはベクトルとして指定されます。

動的計画法アルゴリズムを使用してこの問題を解決するために。次の 2 つの特徴を示すかどうかを尋ねる必要があります。

  1. 最適な部分構造。問題の最適解は、その部分問題の最適解から導き出されますか? たとえば、S(M, N)M 金貨と N 銀貨を使って購入できるアイテムの最大数を とします。S(M, N)再帰関係を使用して導出できますか?
  2. 重複する副問題。S(M, N) の部分問題は、より大きな部分問題を計算するために何度も使用されていますか?

N 行 M 列の 2 次元テーブルを想像してください。の

+---+---+---+---+---+-----+---+
|   | 0 | 1 | 2 | 3 | ... | N |
+---+---+---+---+---+-----+---+
| 0 |   |   |   |   |     |   |
| 1 |   |   |   |   |     |   |
| 2 |   |   |   |   | ... |   |
| 3 |   |   |   |   |     |   |
| : |   |   |   |   |     |   |
| M |   |   |   |   |     |   |
+---+---+---+---+---+-----+---+

私たちのアルゴリズムは基本的にこの表に記入します。行iの列j S[i, j]には、i 金貨と j 銀貨を使用して購入できるアイテムの最大数が示されています。

表を完成させるために、2 つの辞書順に並べ替えられた配列 と を使用できIますD。1 つ目では、ゴールドをプライマリ ソート キーとして、シルバーをセカンダリ キーとして使用します。2番目に、シルバーがプライマリで、ゴールドがセカンダリです。0 番目の行と列に入力するのは簡単です。次に、並べ替えられた 2 つの配列をタンデムでトラバースし、次の再帰を使用してテーブルを完成させることができます。

S[0, 0] = 0
S[i, j] = 0   if i < 0 or j < 0 
S[i, j] = max(S[i-1,j-1] + d[i-1,j-1], S[i-1,j] + d[i-1,j], S[i,j-1] + d[i,j-1])

どこd[i*,j*]は を使用して購入できる追加アイテムの数です。<i,j> - <i*, j*>どこ<i*, j*>は のいずれかです{<i-1, j-1>, <i-1, j>, <i, j-1>}。つまり、残りのお金でどれだけ買えるかということです。これを計算するための検索には、2 つの辞書順に並べ替えられたシーケンス (IまたはD) のいずれかでバイナリ検索を実行することが含まれます。

このソリューションは、計算にO((MN + n)logn)時間かかり、O(MN + n)スペースを使用します。

于 2012-05-09T12:46:21.250 に答える
4

この問題では、すべてのアイテムに 2 次元のコストがあります。アイテム i のコストを c[i] = < a, b > とします。ここで、a は金貨のコスト、b は銀貨のコストです。

アイテム i がアイテム j よりも「高くない」ように、アイテムを部分的に注文できるようになりました。

c[i] = <a, b>    c[j] = <a', b'>  and    a <= a' AND b <= b'

これは部分的な順序であることに注意してください。2 つのアイテム <1, 2> と <2, 1> は、この半順序では比較できません。どちらも他のものより高価ではありません。

残りのすべてのアイテムと比較して「それほど高価ではない」限り、貪欲なアルゴリズムがアイテムを安全に購入できることは明らかですが、比較できないアイテムが複数ある場合は、より多くの分析 (検索など) を行うことができます。必要です。

たとえば、コストが

 <1, 1>
 <2, 1>
 <1, 2>
 <3, 3>

これにより、次の半順序になります。

        <1, 1>
       /      \
     <2, 1>   <1, 2>
         \   /
         <3, 3>

（一番下の最も高価なアイテム）。貪欲なアルゴリズムは、最初に <1, 1> を購入します。その後、<2, 1> と <1, 2> の両方が実行可能な購入オプションです。アルゴリズムが <2, 1> を購入することを選択した場合、次に購入するのは <1, 2> です。これは、残りのすべてのアイテム (<3, 3>) よりも高くないためです。

単純な貪欲なアルゴリズムは失敗する可能性があります。設定 <2, 1>, <1, 2>, <3, 0> および初期のコイン量 金 = 4、銀 = 2 の場合、最適解は <1, 2> および <3, 0> によるものです。 、しかし、最初に<2、1>を購入すると、そのアイテムのみを購入できるようになります（購入には<2、1>コインが残り、残りの2つのアイテムのいずれも購入できません）。

私はこの購入にアプローチし、半順序構造を構築してからバックトラッキング検索を実行します。時間の制約により完全なバックトラッキングが許可されない場合は、貪欲なアルゴリズムのヒューリスティックとして制限されたバックトラッキングを使用します。

于 2012-05-10T06:13:24.470 に答える
-2

「アルゴリズム」はありません。

よく知られている NP 完全問題であるナップザック問題のバージョンについて説明しています。N、M、k が小さい問題の SMALL バージョンでは、すべての異なる組み合わせを実行するだけです。より大きなバージョンの場合、宇宙の寿命より短い時間で計算できる「最適な」解を見つける既知の方法はありません。

これを解決するのに最も近いのは、線形計画法として知られる分野です。それは...簡単なことではありませんが、必要に応じて読んでください。

于 2012-05-08T23:17:31.893 に答える