硬幣兌換問題，每個面額的硬幣數量無限

Question

我想知道硬幣兌換問題算法的思想，其中每個面額都有無限數量的硬幣。指如何應用DP（如標準硬幣找零問題） 比如，對於集1,10,15， 變更爲35給出 - 10 2枚硬幣和15

一個硬幣也給了我的想法暴力強制算法。我知道遍歷所有的集合。但如何改變每個硬幣的數量，同時暴力破解

Answer 1

我會考慮構建解決方案一步一步時，電感：可用

硬幣是1c，5c，10c，25c（你可以根據你的需要調整它們）

1. minimun硬幣1c = 1 x 1c。高達4美分，我們需要1c個硬幣，因爲這是最小的面額。
2. 5美分，我們有一個5c硬幣。結合上面的4c，我們可以生成1到9之間的任何數字。
3. 對於10美分，我們需要1 X 10c。組合上述3中，我們可以產生任何數量的1和19之間
4. 對於20c中，我們需要2×10c中，20是整除10

如果可以感應地制定該問題，它可能更容易處理它。

編輯：
好吧，這裏的另一個試圖解釋動態規劃的解決方案：

與x行的表的思（x是不同教派的數量）n和n列（是你的金額必須建立使用最小面值）。此表中的每個單元格代表一個不同的子問題，並最終包含解決方案。假設：

行1代表一組{1c}即第1行中，你被允許使用無限1c
行2代表組{1c, 10c}即第2行你被允許無限1c和10c
行3代表集{1c, 10c, 15c}依此類推......
每列代表您想要構建的數量。

因此，每個單元對應一個小的子問題。例如（該索引從1開始爲簡單起見），
cell(1, 5) ==>構造5c僅使用{1c}
cell(2, 9) ==>構造9c使用{1c, 10c}
cell(3, 27) ==>構造27c使用{1c, 10c, 15c}
現在您的目標是獲得答案cell(x, n)

Solution:
從最簡單的問題開始求解表格。解決第一行是微不足道的，因爲在第一行中唯一可用的面額是{1c}。第1行中的每個單元格都有一個簡單的解決方案，從而導致cell(1, n) = {nx1c}（n硬幣1c）。

現在進入下一行。對第二行進行推廣，讓我們看看如何解決（說）cell(2, 28)即構造28c使用{1c, 10c}。在這裏，您需要做出決定，是否在解決方案中包含10c以及多少個硬幣。你有3種選擇（3 = 28/10 + 1）

Choice 1：
以{1x10c}，並從以前的行（存儲在cell(1, 18)）休息。這給你{1x10c, 18x1c} = 19 coins

Choice 2：
以{2x10c}和前一行其餘（存儲在cell(1, 8)）。這給你{2x10c, 8x1c} = 10 coins

Choice 3：
不採取任何10c從上一行的剩餘部分（存儲在cell(1, 28)）。這給你{28x1c} = 28 coins

顯然，選擇2是最好的，因爲它需要更少的硬幣。把它寫在桌上，然後繼續。表格一次填充一行，並在一行中按照數量遞增的順序填充。

通過上面的規則走，你會到達cell(x, n)，解決這將是n/p + 1的替代品之間的選擇，其中p =在x行最新的面額。最好的選擇是你的答案。

該表實際上記錄了較小問題的解決方案，因此您不需要一次又一次解決問題。

Answer 2

有關蠻力部分：

int i,j,k; 
for(i=0;i<35;i++){ 
    for(j=0;j<4;j++){ 
    for(k=0;k<3;k++){ 
     if(1*i+10*j+15*k == 35){ 
     //is this what you need? 
     //minimum=min(minimum,(i+j+k)); 
     } 
    } 
    } 
} 

Answer 3

關於蠻力。

它被稱爲「貪婪算法」 - 你總是採取不大於你需要代表的值的最大硬幣。

僞代碼，返回到代表值，如果我們可以使用的次數每一個無限數量

int[] greedy(int value, int[] coins) { 
    int[] ans = ...; 
    int v = coins.length - 1; 
    int left = value; 
    while (left > 0 && v >= 0) { 
     if (coins[v] <= left) { 
      ans.push(coins[v]); 
     } else { 
      v--; 
     } 
    } 
    return left == 0 ? ans : //representation impossible, 
          //so you better do something; 
} 

僞代碼所需要的硬幣數量，返回到表示值所需要的硬幣的數目，如果能夠使用的時候每一個無限數量

int f(int value, int[] coins) { 
    int[] memo = new int[value + 1]; 
    Arrays.fill(memo, 1234567); 
    memo[0] = 0; 
    for (int coin : coins) 
     for (int i = 0; i + coin <= value; i++) 
      memo[i + coin] = min(memo[i + coin], memo[i] + 1); 
    return memo[value]; 
} 

知道該走的硬幣，從月底開始：if memo[value] = 3，那麼你檢查所有的硬幣，發現硬幣等是memo[value - coin] == 2，從(value - coin)繼續下去，直到你達到0。

Answer 4

這是如何將數字從一個編號系統轉換爲另一個編號系統。例如：

35 = 1*2^5 + 0*2^4 + 0*2^3 + 0*2^2 + 0*2^1 + 1*2^0 

即：

var cash = 35; 
var coins = [15, 10, 5, 1]; 
var change = {}; 
for(var i=0; i<coins.length; i++){ 
    change[coins[i]] = Math.floor(cash/coins[i]); 
    cash %= coins[i]; 
} 
//change now contains: 
//15:2, 10:0, 5:1, 1:0 

Answer 5

你可以在這裏運行http://www.exorithm.com/algorithm/view/coin_change

function coin_change ($amount, $coins) 
{ 
    $change = array(); 
    rsort($coins); 
    for($i=0; $i<count($coins); $i++) { 
    $change[$coins[$i]] = floor($amount/$coins[$i]); 
    $amount = $amount % $coins[$i]; 
    } 
    return $change; 
}