3

$6.39 を稼ぐには、以下を選択できます。

  • 5ドル札
  • 1 ドル札が 6 ドルになります。
  • 25¢ コインで $6.25
  • 10¢ コインで $6.35
  • 1¢ コイン 4 枚で $6.39 になります。

ただし、通貨に 1、7、および 10 の重みのコインがある場合は機能しません。私の質問は、貪欲なアルゴリズムが [効率的に] 少数の重みでのみ機能するのはなぜですか? 与えられた重みのセットが貪欲なアルゴリズムを満たし、同時に最適になるために満たすべき条件は何ですか?

4

2 に答える 2

2

この正確な問題は、David Pearson による「A polynomial-time algorithm for the change-making problem」で検討されています。

残念ながら、この質問に答える洗練された数学的特性は提供されません。これは、貪欲なアルゴリズムが機能しない場合、反例は有限数の値の中にあり、これらの値にはそれぞれをチェックするのが安価になるプロパティがあるという事実に基づいています。

于 2013-07-08T15:02:06.317 に答える
0

この記事でいくつかの答えを見つけることができます: http://arxiv.org/pdf/0801.0120v2.pdf

（少なくとも彼らの要約によると、私は論文全体を読んでいません）

于 2013-07-08T08:41:08.327 に答える