变革问题

给定货币系统，是否可以给出一定数量的硬币以及如何找到与该数量相对应的最小硬币组。

**规范货币系统。**对于某些货币系统，就像我们在现实生活中使用的系统一样，直观的解决方案非常有效。例如，如果不同的欧元硬币和账单（不包括美分）是 1€，2€，5€，10€，给出最高的硬币或账单，直到我们达到金额并重复此程序将导致最小的硬币组。

我们可以用 OCaml 递归地做到这一点：

(* assuming the money system is sorted in decreasing order *)
let change_make money_system amount =
  let rec loop given amount =
    if amount = 0 then given
    else 
      (* we find the first value smaller or equal to the remaining amount *)
      let coin = List.find ((>=) amount) money_system in
      loop (coin::given) (amount - coin)
  in loop [] amount

制造这些系统使得改变变得容易。在涉及任意货币制度时，问题变得更加困难。

一般情况。如何用 10 欧元，7 欧元和 5 欧元的硬币给 99€？在这里，给我们 10 欧元的硬币直到我们留下 9 欧元显然没有解决方案。更糟糕的是，解决方案可能不存在。这个问题实际上是非常困难的，但存在混合贪婪和记忆的可接受的解决方案。我们的想法是探索所有可能性并选择硬币数量最少的那个。

为了给出 X> 0 的数量，我们在货币系统中选择一个 P，然后解决与 XP 相对应的子问题。我们尝试这个系统的所有部分。如果存在，则解决方案是导致 0 的最小路径。

这里是对应于此方法的 OCaml 递归函数。如果不存在解，则返回 None。

(* option utilities *)
let optmin x y =
  match x,y with
  | None,a | a,None -> a
  | Some x, Some y-> Some (min x y)

let optsucc = function
  | Some x -> Some (x+1)
  | None -> None

(* Change-making problem*)
let change_make money_system amount =
  let rec loop n =
    let onepiece acc piece =
      match n - piece with
      | 0 -> (*problem solved with one coin*) 
             Some 1
      | x -> if x < 0 then 
               (*we don't reach 0, we discard this solution*)
               None
             else
               (*we search the smallest path different to None with the remaining pieces*) 
               optmin (optsucc (loop x)) acc
    in
    (*we call onepiece forall the pieces*)
    List.fold_left onepiece None money_system
  in loop amount

注意 ：我们可以注意到此过程可能会计算相同值的更改集的几倍。在实践中，使用 memoization 来避免这些重复会导致更快（更快）的结果。