8

コインの最小変更問題は NP 完全問題ですが、コインの特定のセットでは貪欲なアルゴリズム (最初に最大の額面を選択する) が機能します。コインの値を表す一連の整数が与えられた場合、貪欲なアルゴリズムで十分かどうかを判断する最速のアルゴリズムは何ですか? 明白な方法の 1 つは、動的計画法のソリューションを最大額面まで構築し、貪欲な方法よりも優れたソリューションが得られるかどうかを確認することです。しかし、それを検出するためのより高速な「数学的な方法」はありますか?

4

4 に答える 4

1

私は最近、与えられた 2 つの条件が満たされているかどうかを示すように見える 1 つのソリューションを思いつきました。貪欲なアルゴリズムは最適なソリューションを生成します。

a) GCD (1 を除くすべての金種) = 2 番目に小さい金種。

b) 連続する 2 つの金種の合計は、連続する 3 回目の金種未満でなければなりません。

たとえば。c2 + c3 < c4。

(ここで、c1 = 1; c2、c3、c4 は昇順のコインの額面です)。

これが完全な解決策ではないことは理解しています。しかし、この 2 つの条件が満たされていれば、貪欲なアルゴリズムによって最適解が得られると思います。

于 2013-03-06T06:23:48.880 に答える
0

次の選択が目標金額を生成する場合、貪欲なアルゴリズムは機能します: (機能するより複雑なフォーマットがあるかもしれませんが、これは単純で直線的にチェックできます)

1選択されたものを表しましょう。セットは、最大の額面から、次のようになります。

11...1100...00100...00

つまり、最大のものから 0 個以上が選択され、他の 1 つの要素が選択されます。

これが最適である理由は簡単に証明できます。C = 最大のものから選択された s 個の要素とすると、C の任意の要素を置き換える場合は、より低い要素で置き換える必要があるため、C が s 個以下の要素に対して可能な最大の合計を生成することがわかります。 s 個の最大の要素が既に選択されているため、重要な要素です (また、削除すると明らかにコストが削減されます)。C はターゲットよりも小さい値を生成するため (もう 1 つの要素が必要なため)、ターゲットに到達するには少なくとも 1 つの他の要素が必要です。したがって、ターゲットに到達するために必要な要素の最小量は s+1 です。証明を締めくくります。

これを評価するには O(n) が必要です。これは次のように行うことができます: (Java の場合)

int[] sortedCoins = ...;
int sum = 0, selectionCount = 0, i = 0;
for (; i < sortedCoins.length; i++)
{
  sum += sortedCoins[i];
  if (sum >= target) break;
  selectionCount++;
}
sum -= sortedCoins[i]; // we added the element to push us over, so remove it again
for (; i < sortedCoins.length; i++)
{
  if (sum + sortedCoins[i] == target)
    return selectionCount+1;
}
return -1; // not found

ああ、それが許可されているかどうかを確認する必要がある target = 0 の簡単なケースもあります。

上記には目標金額が必要です。多くの目標金額を確認したい場合は、おそらく上記の方法で O(n^2) ですべての可能な合計を生成し、合計をカウントにマップして、ルックアップを行うだけです。存在する場合は値を取得します。

編集：分岐限定

上記の拡張として、また DP の代わりとして、ブランチ アンド バウンドで貪欲に処理されたブルート フォースを提案します。上記と同様の引数を使用すると、bestCoins の値が と の場合、現在のパスをスキップできることがわかります(currentSum + (bestCoins - currentCoins) * currentItem.value) < target。

これは、いくつかの問題では惨めに失敗し、他の問題では素晴らしく機能することに注意してください (適切な解決策をどれだけ早く見つけるかに大きく依存すると思います)。永遠にかかることを避けるために、最小数のコインを最適なソリューション (上記と同様に、ターゲットに到達するまで最初の要素を調べることから導き出される) に格納し、そこから遠く離れたパスを遮断することができます。

正しく実行された場合は、短時間で実行できるはずです。実行が完了して解決策が得られた場合は、最適な解決策が得られます。そうでない場合は、あまり時間を失うことはなく、別のアルゴリズムを実行できます。 DPのように。

于 2013-01-04T18:02:16.270 に答える