貪心算法-紙幣問(wèn)題

從一個(gè)生活問(wèn)題談起　　

先來(lái)看看生活中經(jīng)常遇到的事吧——假設(shè)您是個(gè)土豪，身上帶了足夠的1、5、10、20、50、100元面值的鈔票。現(xiàn)在您的目標(biāo)是湊出某個(gè)金額w，需要用到盡量少的鈔票。　

依據(jù)生活經(jīng)驗(yàn)，我們顯然可以采取這樣的策略：能用100的就盡量用100的，否則盡量用50的……依次類推。在這種策略下，666=6×100+1×50+1×10+1×5+1×1，共使用了10張鈔票。

function main () {  const RMB = [100, 50, 20, 10, 5, 1] // 鈔票金額  const NUM = 6 // 6種面值  let x = 666  let count = 0  for (let i = 0; i < NUM; i++) {    let use = Math.trunc(x / RMB[i])    count += use    x = x - RMB[i] * use    console.log(`${use}張${RMB[i]}`)  }  console.log(`總共需要${count}`)  return count}

這種策略稱為“貪心”：假設(shè)我們面對(duì)的局面是“需要湊出w”，貪心策略會(huì)盡快讓w變得更小。能讓w少100就盡量讓它少100，這樣我們接下來(lái)面對(duì)的局面就是湊出w-100。長(zhǎng)期的生活經(jīng)驗(yàn)表明，貪心策略是正確的。　　

但是，如果我們換一組鈔票的面值，貪心策略就也許不成立了。如果一個(gè)奇葩國(guó)家的鈔票面額分別是1、5、11，那么我們?cè)跍惓?5的時(shí)候，貪心策略會(huì)出錯(cuò)：　

15=1×11+4×1 （貪心策略使用了5張鈔票）

15=3×5 （正確的策略，只用3張鈔票）

為什么會(huì)這樣呢？貪心策略錯(cuò)在了哪里？

鼠目寸光。　

剛剛已經(jīng)說(shuō)過(guò)，貪心策略的綱領(lǐng)是：“盡量使接下來(lái)面對(duì)的w更小”。這樣，貪心策略在w=15的局面時(shí)，會(huì)優(yōu)先使用11來(lái)把w降到4；但是在這個(gè)問(wèn)題中，湊出4的代價(jià)是很高的，必須使用4×1。如果使用了5，w會(huì)降為10，雖然沒(méi)有4那么小，但是湊出10只需要兩張5元。　　

在這里我們發(fā)現(xiàn)，貪心是一種只考慮眼前情況的策略。

那么，現(xiàn)在我們?cè)鯓硬拍鼙苊馐竽看绻饽兀?/p>

重新分析剛剛的例子。w=15時(shí)，我們?nèi)绻?1，接下來(lái)就面對(duì)w=4的情況；如果取5，則接下來(lái)面對(duì)w=10的情況。我們發(fā)現(xiàn)這些問(wèn)題都有相同的形式：“給定w，湊出w所用的最少鈔票是多少?gòu)垼俊苯酉聛?lái)，我們用f(n)來(lái)表示“湊出n所需的最少鈔票數(shù)量”。

這給了我們一個(gè)至關(guān)重要的啟示—— f(n) 只與 f(n -1),f(n - 5),f(n - 11) 相關(guān)， 更確切地說(shuō)：

f(n) = min{f(n -1),f(n - 5),f(n - 11)} + 1

這個(gè)式子是非常激動(dòng)人心的。我們要求出f(n)，只需要求出幾個(gè)更小的f值；既然如此，我們從小到大把所有的f(i)求出來(lái)不就好了？注意一下邊界情況即可。代碼如下：

function coinChange (coins, amount) {  const Max = amount + 1  const dp = new Array(amount + 1)  dp.fill(Max)  dp[0] = 0  for (let i = 1; i <= amount; i++) {    for (let j = 0; j < coins.length; j++) {      if (coins[j] <= i) {        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)      }    }  }  return dp[amount] > amount ? -1 : dp[amount]}console.log(coinChange([1, 5, 11], 15)) // 3種

f(n) 只與 f(n -1),f(n - 5),f(n - 11) 相關(guān)。?

我們只關(guān)心 f(w) 的值，不關(guān)心是怎么湊出w的。

這兩個(gè)事實(shí)，保證了我們做法的正確性。它比起貪心策略，會(huì)分別算出取1、5、11的代價(jià)，從而做出一個(gè)正確決策，這樣就避免掉了“鼠目寸光”！

查看更多：https://leetcode-cn.com/problems/gaM7Ch/solution/zui-shao-de-ying-bi-shu-mu-by-leetcode-s-rm0w/