js動(dòng)態(tài)規(guī)劃找零問(wèn)題

wangym 發(fā)布于2019-08-20 17:14 / 2967人閱讀

摘要：存儲(chǔ)了到的最優(yōu)解的找零是或者或者或者的最優(yōu)解個(gè)數(shù)是最優(yōu)解是子解的子解是的最優(yōu)解的最優(yōu)解的最優(yōu)解的最優(yōu)解類(lèi)推如果剛好找完返回每個(gè)最優(yōu)解存儲(chǔ)起來(lái)

function MinCoinChange(coins) {
  var coins = coins;
  //  cache存儲(chǔ)了1到37的最優(yōu)解
  //  37的找零 是36 或者32  或者27 或者12 的最優(yōu)解個(gè)數(shù)+1
  var cache = {};
  this.makeChange = function(amount) {
    var me = this;
    if (!amount) {
      return [];
    }
    if (cache[amount]) {
      return cache[amount];
    }
    //  min是最優(yōu)解 newMin是子解 36的子解是(35的最優(yōu)解 31的最優(yōu)解 26的最優(yōu)解 11的最優(yōu)解)---->類(lèi)推
    var min = [],
      newMin, newAmount;
    for (var i = 0; i < coins.length; i++) {
      var coin = coins[i];
      newAmount = amount - coin;
      if (newAmount >= 0) {
        //  如果剛好找完 newAmount = 0  返回newMin = [];
        newMin = me.makeChange(newAmount);
      }
      if (newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) {
        min = [coin].concat(newMin);
      } 
    }
    //  每個(gè)最優(yōu)解存儲(chǔ)起來(lái)
    return (cache[amount] = min);
  }
  this.cache = function() {
    console.log(cache);
  }
}
var a = new MinCoinChange([1, 5, 10, 25]);
console.log(a.makeChange(36));

GPU云服務(wù)器云服務(wù)器動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃python java動(dòng)態(tài)規(guī)劃代碼 java零錢(qián)動(dòng)態(tài)規(guī)劃

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/83424.html

相關(guān)文章

前端筆面試中的編程題

摘要：之前是寫(xiě)在面試記錄里的，題目有點(diǎn)開(kāi)始多了就分割出來(lái)專(zhuān)門(mén)來(lái)一篇了實(shí)現(xiàn)一個(gè)函數(shù)，接受一個(gè)參數(shù)，輸出個(gè)遞增自然數(shù)輸出的自然數(shù)不能含有，，或?yàn)榈谋稊?shù)，如果含有或?yàn)榈谋稊?shù)，則輸出下一個(gè)自然數(shù)支持多次調(diào)用，從開(kāi)始，每次自上次調(diào)用的末尾自然數(shù)繼續(xù)打印示例之前是寫(xiě)在面試記錄里的，題目有點(diǎn)開(kāi)始多了就分割出來(lái)專(zhuān)門(mén)來(lái)一篇了實(shí)現(xiàn)一個(gè)函數(shù)printNum，接受一個(gè)參數(shù)n，輸出n個(gè)遞增自然數(shù)· 輸出的自然...

Karuru 2019-08-26 12:18 評(píng)論0 收藏0
JS之?dāng)?shù)據(jù)結(jié)構(gòu)與算法 (5)

摘要：序列文章面試之函數(shù)面試之對(duì)象面試之?dāng)?shù)組的幾個(gè)不操作面試之對(duì)比分析前言數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)組織數(shù)據(jù)的方式算法是系統(tǒng)描述解決問(wèn)題的策略。了解基本的數(shù)據(jù)結(jié)構(gòu)和算法可以提高代碼的性能和質(zhì)量。 showImg(https://segmentfault.com/img/bVbqYZQ?w=3000&h=2250); 序列文章 JS面試之函數(shù)(1)JS面試之對(duì)象(2)JS面試之?dāng)?shù)組的幾個(gè)不low操作...

wangtdgoodluck 2019-08-23 16:48 評(píng)論0 收藏0
現(xiàn)金找零方式的總數(shù)（sicp）

問(wèn)題：現(xiàn)有現(xiàn)金a，并且有n種面額的零錢(qián)，問(wèn)，共有多少種找零方式。問(wèn)題細(xì)化：現(xiàn)有現(xiàn)金1元，并且有50分，25分，10分，5分，1分五種面額，用這5種零錢(qián)組成1元，共有多少種方式？如果把n種零錢(qián)按照某種順序排列（如50分，25分，10分，5分，1分，不一定升序或降序，也可以亂序），那么問(wèn)題可以轉(zhuǎn)化為：現(xiàn)金a用除第一種零錢(qián)之外其他面額的找零方式數(shù)目加上現(xiàn)金a-d用所有面額的找零方式數(shù)目，其中d為第一...

pf_miles 2019-08-22 11:23 評(píng)論0 收藏0
SICP Python 描述 3.2 函數(shù)和所生成的過(guò)程

摘要：函數(shù)和所生成的過(guò)程來(lái)源譯者飛龍協(xié)議函數(shù)是計(jì)算過(guò)程的局部演化模式。在這一章中，我們會(huì)檢測(cè)一些用于簡(jiǎn)單函數(shù)所生成過(guò)程的通用模型。也就是說(shuō)，遞歸函數(shù)的執(zhí)行過(guò)程可能需要再次調(diào)用這個(gè)函數(shù)。 3.2 函數(shù)和所生成的過(guò)程來(lái)源：3.2 Functions and the Processes They Generate 譯者：飛龍協(xié)議：CC BY-NC-SA 4.0 函數(shù)是計(jì)算過(guò)程的局部演化...

lolomaco 2019-07-25 10:47 評(píng)論0 收藏0
比特幣入門(mén)筆記

摘要：也就是說(shuō)，比特幣是一個(gè)完全出于社區(qū)共識(shí)的貨幣。所謂全稱為，它是比特幣交易的基本單位。根據(jù)比特幣的協(xié)議，一個(gè)區(qū)塊的大小是而一筆交易大概是，因此一個(gè)區(qū)塊大概可以包含筆交易。誕生比特幣誕生于 2008 年，一個(gè)網(wǎng)名為中本聰?shù)娜耍岢隽艘粋€(gè)設(shè)想：創(chuàng)造一種不受政府或任何組織控制的貨幣比特幣的本質(zhì)就是一串?dāng)?shù)字，沒(méi)有任何資產(chǎn)支持（現(xiàn)行貨幣背后都是國(guó)家或銀行提供資產(chǎn)支持）。也就是說(shuō)，比特幣是一...

Loong_T 2019-06-27 18:40 評(píng)論0 收藏0