2

我想知道每个面额都有无限数量的硬币的硬币找零问题的算法思想。表示如何应用 DP（如标准硬币找零问题） 例如，在第 1、10、15 组中，找零 35 给--2 个 10 硬币和 1 个 15 硬币

也给我一个蛮力算法的想法。我知道迭代所有的集合。但是如何在暴力破解时改变每个硬币的数量

4

5 回答 5

7

我会考虑一次一步地构建解决方案，归纳：

可用硬币有 1c、5c、10c、25c（您可以根据需要调整它们）

  1. 1c = 1 X 1c 的最小硬币。最多 4 美分，我们需要 1c 硬币，因为那是最小的面额。
  2. 对于 5 美分，我们有一个 5c 硬币。结合上面的 4c，我们可以生成 1 到 9 之间的任何数字。
  3. 对于 10 美分，我们需要 1 X 10c。结合以上三者，我们可以生成 1 到 19 之间的任意数字。
  4. 对于 20c，我们需要 2 x 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:
取 no10c和前一行的其余部分（存储在 中cell(1, 28)）。这给了你{28x1c}=28 coins

显然，选择 2 是最好的，因为它需要更少的硬币。把它写在桌子上，然后继续。表格将一次填满一行，并且在一行内，按照数量增加的顺序。

按照上述规则，您将达到cell(x, n)，解决方案将是在替代方案之间进行n/p + 1选择，其中p= 行中的最新面额x。最好的选择是你的答案。

该表实际上将小问题的解决方案记住了，因此您无需一次又一次地解决它们。

于 2009-10-05T09:33:03.363 回答
3

关于蛮力部分：

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));
      }
    }
  }
}
于 2009-10-05T09:17:33.053 回答
0

你可以在这里运行它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;
}
于 2010-11-02T19:34:57.280 回答
0

这是如何将数字从一种编号系统转换为另一种编号系统的方法。例如：

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
于 2009-10-05T12:01:37.930 回答
0

关于蛮力。

它被称为“贪心算法”——你总是拿最大的硬币，它不大于你需要代表的价值。

伪代码，返回代表价值所需的硬币数量，如果我们可以无限次使用每个硬币

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。

于 2009-10-05T11:51:55.063 回答