找零問題(Coin Change)

1.計算有幾種找零方式

1.遞迴解法

// Returns the count of ways we can sum.

WayOfChange = (S,m,n) => {
  // 此硬幣可兌換
  if(n ===0) {
    return 1;
  }
  // 找不到解
  if(n<0){
    return 0;
  }
  // 沒有硬幣且還有剩餘的錢需兌換，代表尚未找到解答
  if(m<=0 && n>=1){
    return 0;
  }

  // WayOfChange(S,m-1,n) 不包含解
  // WayOfChange(S,m,n-S[m-1]) 至少包含一個解
  return WayOfChange(S,m-1,n) + WayOfChange(S,m,n-S[m-1]);
}


let S =[1,2,3,4];
let m = S.length;
let n = 4;
let result = WayOfChange(S,m,n);
console.log('找零方式：'+ result);

2.找給客戶最少硬幣的計算方式

1.貪婪演算法(Greedy algorithm)

var coins = [1, 3, 4];

makeChange = (amout) => { 
  var change = []; 
  var total = 0;
  // 從貨幣最大的開始找零
  for (var i = coins.length - 1; i >= 0; i--) {
    var coin = coins[i];
    // 當小於或是等於總額時，繼續找零
    while(total + coin <= amout) { 
      change.push(coin); 
      total += coin; 
    } 
   } 
  return change; 
};

var procedure = makeChange(6)
console.log('找零過程:' + procedure)

Reference:

[1]. http://www.algorithmist.com/index.php/Coin_Change

[2].https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/