快捷導(dǎo)航

js貪心算法錢幣找零問(wèn)題代碼實(shí)例

更新時(shí)間：2019年09月11日 11:21:43 作者：Jaxu''s home

這篇文章主要介紹了js貪心算法錢幣找零問(wèn)題代碼實(shí)例,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下

給定一組硬幣的面額，以及要找零的錢數(shù)，計(jì)算出符合找零錢數(shù)的最少硬幣數(shù)量。

例如，美國(guó)硬幣面額有1、5、10、25這四種面額，如果要找36美分的零錢，則得出的最少硬幣數(shù)應(yīng)該是1個(gè)25美分、1個(gè)10美分和1個(gè)10美分共三個(gè)硬幣。這個(gè)算法要解決的就是諸如此類的問(wèn)題。我們來(lái)看看如何用動(dòng)態(tài)規(guī)劃的方式來(lái)解決。

對(duì)于每一種面額，我們都分別計(jì)算所需要的硬幣數(shù)量。具體算法如下：

如果全部用1美分的硬幣，一共需要36個(gè)硬幣
如果用5美分的硬幣，則需要7個(gè)5美分的硬幣 + 1個(gè)1美分的硬幣 = 8個(gè)硬幣
如果用10美分的硬幣，則需要3個(gè)10美分的硬幣 + 1個(gè)5美分的硬幣 + 1個(gè)1美分的硬幣 = 5個(gè)硬幣
如果用25美分的硬幣，則需要1個(gè)25美分的硬幣 + 1個(gè)10美分的硬幣 + 1個(gè)1美分的硬幣 = 3個(gè)硬幣

示意圖

方案4的硬幣總數(shù)最少，因此為最優(yōu)方案。

具體的代碼實(shí)現(xiàn)如下：

function minCoinChange(coins, amount) {
  let result = null;
  if (!amount) return result;

  const makeChange = (index, value, min) => {
    let coin = coins[index];
    let newAmount = Math.floor(value / coin);
    if (newAmount) min[coin] = newAmount;
    if (value % coin !== 0) {
      makeChange(--index, value - coin * newAmount, min);
    }
  };

  const arr = [];
  for (let i = 0; i < coins.length; i++) {
    const cache = {};
    makeChange(i, amount, cache);
    arr.push(cache);
  }
  console.log(arr);
  let newMin = 0;
  arr.forEach(item => {
    let min = 0;
    for (let v in item) min += item[v];
    if (!newMin || min < newMin) {
      newMin = min;
      result = item;
    }
  });
  return result;
}

函數(shù)minCoinChange()接收一組硬幣的面額，以及要找零的錢數(shù)。我們將上面例子中的值傳入：

const result = minCoinChange2([1, 5, 10, 25], 36);
console.log(result);

得到如下結(jié)果：

[
 { '1': 36 },
 { '1': 1, '5': 7 },
 { '1': 1, '5': 1, '10': 3 },
 { '1': 1, '10': 1, '25': 1 }
]
{ '1': 1, '10': 1, '25': 1 }

上面的數(shù)組是我們?cè)诖a中打印出來(lái)的arr的值，用來(lái)展示四種不同面額的硬幣作為找零硬幣時(shí)，實(shí)際所需要的硬幣種類和數(shù)量。最終，我們會(huì)計(jì)算arr數(shù)組中硬幣總數(shù)最少的那個(gè)方案，作為minCoinChange()函數(shù)的輸出。

當(dāng)然在實(shí)際應(yīng)用中，我們可以把硬幣抽象成任何你需要的數(shù)字，這個(gè)算法能給出你滿足結(jié)果的最小組合。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: