js貪心算法錢幣找零問題代碼實(shí)例-創(chuàng)新互聯(lián)

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

宜城網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián)建站,宜城網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為宜城成百上千家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站制作要多少錢，請找那個售后服務(wù)好的宜城做網(wǎng)站的公司定做！

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

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

1. 如果全部用1美分的硬幣，一共需要36個硬幣
2. 如果用5美分的硬幣，則需要7個5美分的硬幣 + 1個1美分的硬幣 = 8個硬幣
3. 如果用10美分的硬幣，則需要3個10美分的硬幣 + 1個5美分的硬幣 + 1個1美分的硬幣 = 5個硬幣
4. 如果用25美分的硬幣，則需要1個25美分的硬幣 + 1個10美分的硬幣 + 1個1美分的硬幣 = 3個硬幣

示意圖

方案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;
}

文章題目：js貪心算法錢幣找零問題代碼實(shí)例-創(chuàng)新互聯(lián)
瀏覽地址：http://bm7419.com/article10/dssgdo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開發(fā)、品牌網(wǎng)站建設(shè)、商城網(wǎng)站、虛擬主機(jī)、定制開發(fā)、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)