algorithm - 为什么贪心硬币找零算法对某些硬币组不起作用？

Question

我了解硬币找零问题的贪心算法（用尽可能少的硬币支付特定金额）是如何工作的——它总是选择面额最大的硬币，但不超过剩余的总和——并且它总能找到正确的解决方案特定的硬币套装。

但是对于某些硬币组，贪心算法会失败。例如，对于集合{1, 15, 25}和总和 30，贪心算法首先选择 25，余数为 5，然后是 5 个 1，总共有 6 个硬币。但是硬币数量最少的解决方案是两次选择 15。

一组硬币必须满足什么条件才能使贪心算法找到所有和的最小解？

Answer 1

形成拟阵（https://en.wikipedia.org/wiki/Matroid）的集合可用于通过使用贪婪方法来解决硬币更换问题。简而言之，拟阵是满足以下条件的有序对 M = (S,l)：

1. S 是有限非空集
2. l 是 S 的一个非空子集族，称为独立子集，使得如果 B->l 且 A 是 B 的子集，则 A -> l
3. 如果 A-> l, B-> l 和 |A| < |B|，则存在某个元素 x-> BA 使得 AU {x} ->l

在我们的硬币兑换问题中，S 是一组所有硬币的降序价值 我们需要通过 S 中的最小硬币数量来达到 V 的值

在我们的例子中，l 是一个包含所有子集的独立集合，使得以下对于每个子集都成立：它们中的值的总和是 <=V

如果我们的集合是拟阵，那么我们的答案是 l 中的最大集合 A，其中没有 x 可以进一步添加

为了检查，我们看看拟阵的性质是否在集合 S = {25,15,1} 其中 V = 30 现在，在 l 中有两个子集：A = {25} 和 B= {15,15} 因为|一个| < |B|，则存在某个元素 x-> BA 使得 AU {x} ->l (根据 3) 所以，{25,15} 应该属于 l，但它是矛盾的，因为 25+15>30

所以，S 不是拟阵，因此贪婪的方法对它不起作用。

Answer 2

在任何情况下，如果没有硬币的价值，当添加到最低面额时，低于立即小于它的面额的两倍，贪心算法就会起作用。

即 {1,2,3} 有效，因为 [1,3] 和 [2,2] 添加到相同的值，但是 {1, 15, 25} 无效，因为（对于更改 30）15+15>25 +1

Answer 3

如果贪心算法给出的硬币数量对于所有数量都是最优的，那么硬币系统就是规范的。

本文提供了一种 O(n^3) 算法来确定硬币系统是否规范，其中 n 是不同种类硬币的数量。

对于非规范硬币系统，c贪心算法产生的硬币数量是次优的；c称为反例。如果最小的反例大于最大的单个硬币，则硬币系统是紧密的。

Answer 4

这是一个反复出现的问题。给定一组硬币{Cn, Cn-1, . . ., 1}，对于1 <= k <= n, Ck > Ck-1，如果 Ck > Ck-1 + Ck-2 ，贪婪算法将产生最小数量的硬币，对于价值V=(Ck + Ck-1) - 1，将贪婪算法应用于硬币子集{Ck, Ck-1, . . ., 1}，其中Ck <= V，导致更少硬币比将贪心算法应用于硬币子集所产生的数字{Ck-1, Ck-2, . . ., 1}。

测试很简单：对于 `1 <= k <= n 测试贪心算法在 Ck + Ck-1 - 1 的值下产生的硬币数量。对硬币集 {Ck, Ck-1, . . ., 1} 和 {Ck-1, Ck-2, . . ., 1}. 如果对于任何 k，后者产生的硬币比前者少，则贪心算法将不适用于该硬币组。

例如，当 n=4 时，考虑硬币集合 {C4, C3, C2, 1} = {50,25,10,1}。从 k=n=4 开始，然后 V = Cn + Cn-1 - 1 = 50+25-1 = 74 作为测试值。对于 V=74，G{50,25,10,1} = 7 个硬币。G{25, 10, 1} = 8 个硬币。到目前为止，一切都很好。现在让 k=3。那么V=25+10-1=34。G{25, 10, 1} = 10 个硬币，但 G{10, 1} = 7 个硬币。所以，我们知道贪心算法不会最小化硬币集合 {50,25,10,1} 的硬币数量。另一方面，如果我们在这个硬币组中添加镍，G{25, 10, 5, 1} = 6 和 G{10, 5, 1} = 7。同样，对于 V=10+5-1= 14，我们得到 G{10, 5, 1} = 5，但 G{5,1} = 6。所以，我们知道，Greedy 适用于 {50,25,10,5,1}。

这就引出了一个问题：硬币的面额应该是什么，满足贪婪算法，这会导致从 1 到 100 的任何值的硬币的最小最坏情况数？答案很简单：100 个硬币，每个硬币的值从 1 到 100 不同。可以说这不是很有用，因为它在每笔交易中线性搜索硬币。更不用说铸造这么多不同面额并跟踪它们的费用了。

现在，如果我们想首先最小化面额的数量，而其次最小化由 Greedy 产生的从 1 到 100 的任何值的硬币的最终数量，那么面额为 2 的硬币：{64,32,16,8,4 , 2, 1} 对于任何值 1:100（值小于十进制 100 的 7 位数字中的最大 1 数），最多产生 6 个硬币。但这需要 7 个面额的硬币。五个面额 {50, 25, 10, 5, 1} 的最坏情况是 8，这发生在 V=94 和 V=99。3 {1, 3, 9, 27, 81} 次方的硬币也只需要 5 个面额即可被 Greedy 使用，但在最坏的情况下也会产生 8 个硬币的值分别为 62 和 80。最后，使用任何 5 个面额{64, 32, 16, 8, 4, 2, 1} 的子集，不能排除“1”，并且满足贪婪，也将导致最多 8 个硬币。所以存在线性权衡。将面额的数量从 5 增加到 7 会分别将表示 1 到 100 之间的任何值所需的最大硬币数量从 8 减少到 6。

另一方面，如果你想尽量减少买卖双方交换硬币的数量，假设每个人的口袋里至少有一个每种面额的硬币，那么这个问题相当于平衡任何硬币所需的最小重量。重量从 1 磅到 N 磅。事实证明，如果硬币面额以 3 的幂为单位给出，则购买时兑换的硬币数量最少：{1, 3, 9, 27, . . .}。

请参阅https://puzzling.stackexchange.com/questions/186/whats-the-fewest-weights-you-need-to-balance-any-weight-from-1-to-40-pounds。

Answer 5

那么我们真的需要重新表述这个问题......贪婪算法本质上是它试图使用提供的硬币面额获得目标值。您对贪心算法所做的任何更改都只会更改达到目标值的方式。它不考虑使用的最少硬币......为了更好地解决这个问题，不存在安全的移动。较高面额的硬币可能会迅速产生目标价值，但这不是一个安全的举动。示例 {50,47,51,2,9} 获得 100 贪婪的选择是拿最高面额的硬币更快地达到 100.. 51+47+2 很好，但是 50+50 应该可以..

让我们取 {50,47,51,9} 来获得 100 如果它贪婪地选择最高的硬币 51，它需要从集合中得到 49。它不知道这是否可能。它试图达到 100 但它做不到 改变贪婪选择只会改变达到 100 的方式这些类型的问题会创建一组解决方案和决策树分支的形式。

Answer 6

理论：

如果贪心算法总是为给定的一组硬币产生一个最佳答案，那么你说这组是canonical。

尽可能简洁地陈述最知名的算法测试 [O(n^3)] 以确定任意一组 n 个硬币是否是规范的：

[c1,c2,..cn] is canonical iff for all w_ij |G(w_ij)| = |M(w_ij)|, 1 < i <= j <= n 

哪里[c1,c2,...cn]是按降序排列的硬币面额列表cn = 1

G(x)表示在输入 上运行贪心算法的硬币向量结果x，（返回为的计数[a1, a2,..., an]在哪里）aici

M(x)表示x使用最少硬币的硬币向量表示

|V|表示硬币向量的大小V：向量中硬币的总数

并且是在将其第 'th 个硬币增加 1 并将其所有硬币计数从到归零之后w_ij产生的硬币向量的评估值。G(c_(i-1) - 1)jj+1n

实现（JavaScript）：

/**
 * Check if coins can be used greedily to optimally solve change-making problem
 * coins: [c1, c2, c3...] : sorted descending with cn = 1
 * return: [optimal?, minimalCounterExample | null, greedySubOptimal | null] */
function greedyIsOptimal(coins) {
  for (let i = 1; i < coins.length; i++) {
    greedyVector = makeChangeGreedy(coins, coins[i - 1] - 1)
    for (let j = i; j < coins.length; j++) {
      let [minimalCoins, w_ij] = getMinimalCoins(coins, j, greedyVector)
      let greedyCoins = makeChangeGreedy(coins, w_ij)
      if (coinCount(minimalCoins) < coinCount(greedyCoins))
        return [false, minimalCoins, greedyCoins]
    }
  }
  return [true, null, null]
}

// coins [c1, c2, c3...] sorted descending with cn = 1 => greedy coinVector for amount
function makeChangeGreedy(coins, amount) {
  return coins.map(c => {
    let numCoins = Math.floor(amount / c);
    amount %= c
    return numCoins;
  })
}
// generate a potential counter-example in terms of its coinVector and total amount of change
function getMinimalCoins(coins, j, greedyVector) {
  minimalCoins = greedyVector.slice();
  minimalCoins[j - 1] += 1
  for (let k = j; k < coins.length; k++) minimalCoins[k] = 0
  return [minimalCoins, evaluateCoinVector(coins, minimalCoins)]
}
// return the total amount of change for coinVector
const evaluateCoinVector = (coins, coinVector) =>
  coins.reduce((change, c, i) => change + c * coinVector[i], 0)

// return number of coins in coinVector
const coinCount = (coinVector) =>
  coinVector.reduce((count, a) => count + a, 0)

/* Testing */
let someFailed = false;
function test(coins, expect) {
  console.log(`testing ${coins}`)
  let [optimal, minimal, greedy] = greedyIsOptimal(coins)
  if (optimal != expect) (someFailed = true) && console.error(`expected optimal=${expect}
  optimal: ${optimal}, amt:${evaluateCoinVector(coins, minimal)}, min: ${minimal}, greedy: ${greedy}`)
}
// canonical examples
test([25, 10, 5, 1], true) // USA
test([240, 60, 24, 12, 6, 3, 1], true) // Pound Sterling - 30
test([240, 60, 30, 12, 6, 3, 1], true) // Pound Sterling - 24
test([16, 8, 4, 2, 1], true) // Powers of 2
test([5, 3, 1], true) // Simple case

// non-canonical examples
test([240, 60, 30, 24, 12, 6, 3, 1], false) // Pound Sterling
test([25, 12, 10, 5, 1], false) // USA + 12c
test([25, 10, 1], false) // USA - nickel
test([4, 3, 1], false) // Simple cases
test([6, 5, 1], false)

console.log(someFailed ? "test(s) failed" : "All tests passed.")

Answer 7

今天，我在 Codeforces 上解决了类似的问题（链接将在最后提供）。我的结论是，要通过贪心算法解决硬币找零问题，它应该满足以下条件：-

1.按升序排序硬币值时，所有大于当前元素的值都应能被当前元素整除。

例如硬币 = {1, 5, 10, 20, 100}，这将给出正确答案，因为 {5,10,20,100} 都可以被 1 整除，{10,20, 100} 都可以被 5 整除，{ 20,100} 都可以被 10 整除，{100} 都可以被 20 整除。

希望这能提供一些想法。

996 A - 中彩票 https://codeforces.com/blog/entry/60217

Answer 8

一个容易记住的例子是任何一组硬币，如果它们按升序排序并且你有：

coin[0] = 1
coin[i+1] >= 2 * coin[i], for all i = 0 .. N-1 in coin[N]

然后使用这种硬币的贪心算法将起作用。

根据您查询的范围，可能会有更优化的（就所需硬币数量而言）分配。例如，如果您正在考虑范围 (6..8) 并且您有硬币 <6, 7, 8> 而不是 <1, 2, 4, 8>。

在 N+ 上完成的最有效的硬币分配是在上述规则集相等的情况下，给你硬币 1、2、4、8 ...；这仅仅是任何数字的二进制表示。从某种意义上说，碱基之间的对话本身就是一种贪心算法。

Max Rabkin 在本次讨论中提供了关于 >= 2N 不等式的证明：http: //olympiad.cs.uct.ac.za/old/camp0_2008/day1_camp0_2008_discussions.pdf