0

一旦机器接管，每枚硬币的面额将是 2 的幂：1 美分、2 美分、4 美分、8 美分、16 美分等。硬币的数量没有限制可以是值得的。

如果硬币的价值之和为n，则一组硬币改变n。例如，以下集合对 7 进行更改：

7 1 美分硬币 5 1 美分，1 2 美分硬币 3 1 美分，2 2 美分硬币 3 1 美分，1 4 美分硬币 1 1 美分，3 2 美分硬币 1 1 美分， 1 2 美分，1 4 美分硬币因此，有 6 种方法可以为 7 找零。

编写一个函数 count_change，它接受一个正整数 n，并返回使用这些未来硬币为 n 找零的方法数。

我一直在研究这个问题一个小时，试图使用树递归，但它不起作用。我正在考虑使用当前金额的 2 个分支 - 1 和当前金额 - 可能的最大硬币价值，但结果永远无法满足。

请给我一个如何处理它的建议......谢谢！

4

1 回答 1

0

这是动态规划的一个例子

您可以使用动态编程的标准公式来实现它（请参阅Coin Change Problem）

让s = {1,5,10,25}我们的硬币现在成为标准硬币面额

让f(x,y) = number_of_ways_to_make_change让x=change_due;y=allowed_coinset_index

  • 注意：如果 y == 0 我们允许的币集是 {1}，如果 y == 1 我们允许的币集是 {1,5} ...
  • 当我们的硬币集仅包含 {1} 时，任何 change_due 都有一个简单的解决方案 1，也就是说，如果你只有便士，那么只有一种方法可以进行更改（所有便士）
  • 尔格f(anything,0) == 1 && f(0,anything) == 1 && f(anything,anthing < 0) == 0

让我们解决一些 change_due 值

change_due   function_call    
1             f(1,0) = 1
...
4             f(4,0) = 1
5             f(5,1) = f((5-5),1) + f(5,0) = 1 + 1 = 2
...
9             f(9,1) = f(9-5,1)+f(9,0) = f(4,1) + 1 = f(4,0*) + 1 = 1+1 = 2
10            f(10,2) = f(10-10,2) + f(10,1) = f(0,2) + (f(5,1)+f(10,0))= 1+(2+1) = 4

所以我们可以看到我们的基本情况

f(x,0) = f(0,y) = 1
f(x is less than zero,y) = f(x,y is less than zero) = 0

请注意，这适用于任何一组硬币

V这是重要的部分V

#if x,y are not in above conditions we want to recursively call ourselves allowing us to build up to a complex solution from several simpler solutions
f(x,y) = f(x-CHANGE_DENOM,y) + f(x,y-1)

让我们继续从上面玩那张桌子，看看我们有多少种方法可以赚到 16 美分

S = [1,5,10,25] 
# our y is 2 (since S[2] = 10 which is the largest denomination < our change_due(16))
f(16,2) = f(16-S[2],2) + f(16,1) 
        = f(16-10,2) + f(16,1) = f(6,2) + f(16,1)
   f(6,2) = f(6-S[2]) + f(6,1) = 0 + f( 6,1) = 0+2#(see below) =
   f(16,1) = f(16-S[1],1) + f(16,0) = f(11,1) + 1
       f(11,1) = f(11-S[1],1) + f(11,0) = f(6,1) + 1
          f(6,1) = f(6-S[1],1) + f(6,0) = f(1,1) + 1
             f(1,1) = f(1-S[1],1) + f(1,0) = 0 + 1 = 1
          f(6,1) = f(1,1) + 1 = 1 + 1 = 2
       f(11,1) = f(6,1) + 1 = 2 + 1 = 3
   f(16,1) = f(11,1) + 1 = 3+1 = 4
f(16,2) = f(6,2) + f(16,1) = 2 + 4  = 6 ways to make change for 16 cents

现在你只需要让它适用于你更大的硬币集

于 2014-02-18T23:19:36.440 回答