變革問題

給定貨幣系統，是否可以給出一定數量的硬幣以及如何找到與該數量相對應的最小硬幣組。

**規範貨幣系統。**對於某些貨幣系統，就像我們在現實生活中使用的系統一樣，直觀的解決方案非常有效。例如，如果不同的歐元硬幣和賬單（不包括美分）是 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 來避免這些重複會導致更快（更快）的結果。