1

私はセントで無制限の 4 種類のコインを持っています: [1, 5, 25, 50]. 正確な 1 ドルの変更を行うために正確な 48 枚のコインを選ぶ方法は? (いずれかの有効な方法で)

これを再帰的に解決する方法は知っていますが、DP を使用して解決することは可能ですか? どのように？ありがとう！

4

2 に答える 2

1

作りたいと思うと、各コインn centsの無限の供給が与えられます。S = { S1, S2, S3, .. Sm }

動的計画法のアプローチ:

ソリューションの総数を数えるには、すべてのセットのソリューションを2 つのセットに分割できます。

  1. を含まないソリューションmth coin (or Sm)。
  2. を含むソリューションat least one Sm。

count(S[], m, n)を解の数を数える関数とすると、との和として書ける。count(S[], m-1, n)count(S[], m, n-Sm)

したがって、次のように定式化されます

count(n,m) = count(n, m-1) + count(n- sm, m)

次の基本ケースを使用します。

  1. count(n,m) =1, n=0、1 つの解決策 -- お金がありません。問題を解決する方法は 1 つだけです - コインの変更を選択しないか、より正確には、0 のコインの変更を選択する

  2. count(n,m) =0, n<0、解なし -- 負の金額

  3. count(n,m) =1, n>=1, m<=0、解決策はありません -- お金はありますが、おつりがありません

于 2015-11-08T06:06:30.063 に答える
1

可能な解決策は次のとおりです（Haskell）：

change d coins | null coins = []
               | d==0 = []
               | d>=coin = coin:change (d-coin) coins           
               | otherwise = change d (tail coins) where
        coin = head coins

ご了承ください：

  1. 与えられたソリューションは、コインのリストが降順でソートされていることを前提としています
  2. 指定された値を変更できない場合は処理されません-チェックを含めなかっただけで、アイデアを実証するだけです
  3. 変更する入力値はセントです

以下にいくつかの結果を示します。

*Main> change 100 [50, 25, 5, 1]
[50,50]
*Main> change 99 [50, 25, 5, 1]
[50,25,5,5,5,5,1,1,1,1]
*Main> change 75 [50, 25, 5, 1]
[50,25]

ソリューションで使用するコインの数に制限がある場合:

exactChange d coins n
    | d==0 && n==0 = [[]]
    | d>0 && n==0 = []
    | d==0 && n>0 = []
    | null coins = []
    | d>=coin = useFirstCoinSolutions ++ skipFirstCoinSolutions
    | otherwise = skipFirstCoinSolutions where
    coin = head coins
    rest = tail coins
    useFirstCoinSolutions = map (\x->coin:x) $ exactChange (d-coin) coins (n-1)
    skipFirstCoinSolutions = exactChange d rest n

これにより、次の結果が得られます。

*Main> exactChange 100 [50, 25, 5, 1] 48
[[25,25,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[25,5,5,5,5,5,5,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[5,5,5,5,5,5,5,5,5,5,5,5,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]

したがって、正確な 48 コインで 100 セントを変更するためのすべての可能なソリューションが得られます。

説明

  1. 最初の条件 d==0 && n==0 は、単一の解決策が見つかったことを定義します。変更する金額はゼロであり、変更に含めるコインはゼロです。
  2. 次の 3 つの条件は、解が見つからないことを定義します。
  3. d>=coin これは、指定された金額が一連のコインの最初のコインよりも高いことを意味するため、ここではオプションが必要です: 最初のコインでソリューション検索を続行するか、セットの最初のコインなしで続行するか
  4. 最初のコインが金額よりも高い場合は、最初のコインを使用せずに進むことができます
于 2015-11-08T06:08:09.377 に答える