硬币兑换问题，每个面额的硬币数量无限

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