硬币更换问题与每个面额的无限数量的硬币-Java 学习之路

我想知道硬币变化问题的算法的想法，其中每个面额具有infinte数量的硬币 . 意味着如何应用DP（如标准的硬币更换问题）例如在第1,10,15组中，更改为35给出 - 2个硬币10和1个硬币15

还给我一个强制算法的想法 . 我知道迭代所有集合 . 但是如何在强制执行时改变每枚硬币的数量

5 回答

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

可用的硬币是1c，5c，10c，25c（你可以根据需要调整它们）
- 最小硬币为1c = 1 X 1c . 高达4美分，我们需要1c硬币，因为这是最少的面额 .
- 5美分，我们有一个5c硬币 . 将其与上面的4c相结合，我们可以生成1到9之间的任何数字 .
- 10美分，我们需要1 X 10c . 结合以上三种，我们可以生成1到19之间的任何数字 .
- 对于20c，我们需要2 x 10c，因为20可以被10整除 .
如果你可以归纳地解决问题，那么解决它可能会更容易 .

EDIT:
好的，这是解释动态编程解决方案的另一种尝试：

可以想象一个包含 x 行的表（ x 是不同面额的数量）和 n 列（ n 是您必须使用最少面额构建的数量） . 此表中的每个单元代表一个不同的子问题，最终将包含解决方案 . 假设：

第1行表示集合 {1c} ，即在第1行中，您可以使用无限 1c
第2行表示集合 {1c, 10c} ，即第2行允许无限 1c 和 10c
第3行代表集 {1c, 10c, 15c} 等等......
每列代表您要构建的金额 .

因此，每个单元对应于一个小的子问题 . 例如（为简单起见，索引从1开始），
cell(1, 5) ==>仅使用 {1c} 构造 5c
cell(2, 9) ==>使用 {1c, 10c} 构造 9c
cell(3, 27) ==>使用 {1c, 10c, 15c} 构造 27c
现在你的目标是得到答案 cell(x, n)

Solution:
从最简单的问题开始解决这个问题 . 解决第一行是微不足道的，因为在第一行中唯一可用的面额是 {1c} . 第1行中的每个单元格都有一个简单的解决方案，导致 cell(1, n) = {nx1c} （ n 硬币 1c ） .

现在进入下一行 . 推广第二行，让我们看看如何解决（比方说） cell(2, 28) 即使用 {1c, 10c} 构造 28c . 在这里，您需要做出决定，是否在解决方案中包含 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 中的最新面额 . 最好的选择是你的答案 .

该表实际上记住了解决较小问题的解决方案，因此您不需要一次又一次地解决它们 .
回复于 2024-04-29T17:52:17+08:00

关于蛮力部分：

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

回复于 2024-04-29T17:52:17+08:00

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

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

回复于 2024-04-29T17:52:17+08:00

关于蛮力 .

它被称为“贪婪算法” - 你总是拿最大的硬币，它不大于你需要代表的 Value .

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

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 .

回复于 2024-04-29T17:52:17+08:00

你可以在这里运行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;
}

回复于 2024-04-29T17:52:17+08:00

硬币更换问题与每个面额的无限数量的硬币

5 回答

相关问题