js動態(tài)規(guī)劃找零問題

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

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

function MinCoinChange(coins) {
  var coins = coins;
  //  cache存儲了1到37的最優(yōu)解
  //  37的找零 是36 或者32  或者27 或者12 的最優(yōu)解個數(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)解)---->類推
    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);
      } 
    }
    //  每個最優(yōu)解存儲起來
    return (cache[amount] = min);
  }
  this.cache = function() {
    console.log(cache);
  }
}
var a = new MinCoinChange([1, 5, 10, 25]);
console.log(a.makeChange(36));

云服務器 GPU云服務器動態(tài)規(guī)劃動態(tài)規(guī)劃python java動態(tài)規(guī)劃代碼 java零錢動態(tài)規(guī)劃

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

轉(zhuǎn)載請注明本文地址：http://hztianpu.com/yun/83424.html

前端筆面試中的編程題

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

Karuru 2019-08-26 12:18 評論0 收藏0
JS之數(shù)據(jù)結(jié)構與算法 (5)

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

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

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

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

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

lolomaco 2019-07-25 10:47 評論0 收藏0
比特幣入門筆記

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

Loong_T 2019-06-27 18:40 評論0 收藏0