7

私はいくつかの動的プログラミングの問題を検討してきましたが、変更するコインの最小数を見つけることに関して、いくつかのコードに頭を悩ませていました。

25、10、および 1 の価値があるコインがあり、30 を変更するとします。貪欲は 25 と 5(1) を返しますが、最適解は 3(10) を返します。この問題に関する本のコードは次のとおりです。

def dpMakeChange(coinValueList,change,minCoins):
   for cents in range(change+1):
      coinCount = cents
      for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents-j] + 1 < coinCount:
               coinCount = minCoins[cents-j]+1
      minCoins[cents] = coinCount
   return minCoins[change]

誰かがこのコードに頭を悩ませるのを手伝ってくれたら (4 行目で混乱し始めます)、それは素晴らしいことです。ありがとう！

4

3 に答える 3

5

コードが目標セント値までのすべてのセント値の問題を解決しているように見えます。目標値vとコインのセットが与えられた場合、最適なコインのC選択Sは の形式union(S', c)でなければならないことがわかります。したがって、問題には最適な部分構造があります。動的計画法のアプローチは、考えられるすべての部分問題を解決することです。直接的な解決策を総当たりしようとすると、はるかに迅速に爆発するものとは対照的に、それは段階を踏む必要があります.cCS'v - value(c)cents * size(C)

def dpMakeChange(coinValueList,change,minCoins):
   # Solve the problem for each number of cents less than the target
   for cents in range(change+1):

      # At worst, it takes all pennies, so make that the base solution
      coinCount = cents

      # Try all coin values less than the current number of cents
      for j in [c for c in coinValueList if c <= cents]:

            # See if a solution to current number of cents minus the value
            # of the current coin, with one more coin added is the best 
            # solution so far  
            if minCoins[cents-j] + 1 < coinCount:
               coinCount = minCoins[cents-j]+1

      # Memoize the solution for the current number of cents
      minCoins[cents] = coinCount

   # By the time we're here, we've built the solution to the overall problem, 
   # so return it
   return minCoins[change]
于 2012-12-07T01:43:46.327 に答える
4

グラフ理論に慣れている場合に役立つ可能性のある、コインの変化の問題について考える方法を次に示します。

次のように定義されたグラフがあるとします。

  • 0 から関心のある値 (例: 39 セントなど) までのすべてのお金の単位 (例: ペニー) に対して 1 つのノードがあります。
  • 使用が許可されているコインの値だけ離れた任意の 2 つのノード間に 1 つのアークがあります (たとえば、ニッケルの使用が許可されている場合、34 セントから 29 セントの間のノード)。

コインの数はパス内のアークの数とまったく同じになるため、コインの変更の問題は、関心のある値からゼロまでの最短経路の問題と考えることができます。

アルゴリズムはグラフ理論の用語を使用しませんが、基本的に同じことを行っています: 外側のループはすべての「セント」(グラフ理論のフレームワークではノード) にまたがっており、内側のループはすべての「セント」に及んでいます。現在のアークから次のアークまでのアーク (coinValueList の値)。全体として、彼らはゼロから関心のある値までの最短経路を探しています。(ゼロまでの値、ゼロから値までの値は問題ではありません。ただし、従来はゼロに向かって下方向に検索します。)

動的計画法を本当に理解し始めたのは、多くの問題がグラフの問題としてキャストできることに気付いたときだけです。（ただし、すべてができるわけではないことに注意してください。ハイパーグラフもあれば、そうでないものもあります。しかし、それは私を大いに助けました。）

于 2012-12-08T20:43:24.473 に答える
3

Python はリスト内包表記で選択/フィルタリングできますが、標準式(transform(x) for x in iterable if condition(x))では同じことができないため、4 行目はわかりにくいと思います。for x in iterable:

したがって、人々が回避する1つの（安っぽいイモ）方法は、2つを一緒に溶接することです. 彼らは、節をc for c in coinValueList追加できるようにするためだけに、実際には変換を行わないリスト内包表記 (したがって ) を作成します。そして、それを標準式if c <= centsのイテラブルとして使用します。for x in iterable:あなたの混乱の一部はそこから来ているのではないかと思います。

その行を書く別の方法は次のとおりです。

...
for eachCoinValue in filter(lambda x: x <= cents, coinValueList):
...

または、さらに明確に、「意図を明らかにする変数」を使用すると、次のようになります。

...
smallEnoughCoins = filter(lambda each: each <= cents)
for each in smallEnoughCoins:
    ...
于 2012-12-07T01:53:49.283 に答える