为什么贪心硬币找零算法对某些硬币集合无效？

Question

为什么贪心硬币找零算法对某些硬币集合无效？

algorithmgreedycoin-change

102

我了解贪心算法用于硬币找零问题（以最少的硬币支付特定金额）的工作原理-它总是选择面额不超过剩余总额的最大硬币，并且它始终可以找到特定硬币集合的正确解决方案。

但是对于某些硬币集合，存在一些总和使得贪心算法无法找到最优解。例如，对于集合{1、15、25}和总和30，贪心算法首先选择25，剩下5元，然后选五个1元硬币，总共需要六枚硬币。但是实际上最少的硬币数解决方案是选择15两次。

硬币集合必须满足什么条件才能使贪心算法在所有总额中找到最小解？

- user1311286

3

答案很大程度上取决于算法的作用: 如果涉及硬币贪心，你需要告诉我们算法是做什么的以及如何实现。请提供相关细节和描述。 - Sergey Kalinichenko

2

算法实际要解决的问题是什么？ - user541686

2

好的，我猜我没有正确提问。要使算法无法工作，一组面值需要满足什么条件？例如，从（25、15、1）中组成30美分，贪心算法给出了25,1,1,1,1,1，但使用两个15更好。那么，25、15和1会使贪心算法失效吗？ - user1311286

2

这是一个好问题，不确定为什么会被踩。他/她想要解释一组硬币必须满足的限制条件，以便贪心算法（始终选择适合的最大硬币）选择最少的硬币来支付任何指定金额。 - j_random_hacker

2

@j_random_hacker 这可以从OP的评论中推断出来，但不能从问题本身中得知算法应该做什么，因此这不是一个好问题。 - Daniel Fischer

显示剩余4条评论

8个回答

14

在任何没有硬币的情况下，其价值加上最小面额仍低于比它小一级的面额的两倍时，贪心算法都是适用的。

例如，{1,2,3} 是适用的，因为[1,3]和[2,2]相加的结果相同。然而，{1,15,25} 不适用，因为（对于找零30），15 + 15>25 + 1。

- Robert Herriott

1

好的答案。这就是我在寻找的 :) - Adam Van Oijen

2

通过测试可以保证贪心算法可行，但反过来不一定成立。贪心算法适用于{1, 5, 15, 25}。 - lhhong

23

这个答案似乎是错误的。即使8 + 8 = 16 < 21 = 20 + 1，但对于硬币{1, 8, 20}和目标值为24，贪心算法并不能给出最优解。 - Alex Yursha

5

我不理解，这个回答完全是错误的？为什么会有这么多赞？我错过了什么吗？ - Ayush

10

一个硬币系统是规范的，如果贪心算法找零所给出的硬币数量对于所有金额都是最优的。

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

对于一个非规范的硬币系统，存在一个金额 c，贪心算法得到的硬币数量不是最优的；c 被称为反例。重要的是，非规范的硬币系统将有一个 c，它比两个最大硬币的面值之和要小，因此可以在有限时间内找到它。

另外，一个硬币系统被称为 "紧密的"，如果它的最小反例大于最大的单个硬币。

- Lohitaksh Trehan

1

它还引用了其他测试，包括最小反例必须低于两个最大硬币的总和这一事实。 - Hans Olsson

1

这个答案看起来是正确的，但是显而易见。"如果一个硬币系统通过了成为规范的测试，那么它就是规范的"（必须提到XKCD https://xkcd.com/703/）。 - Zags

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。因此，我们知道贪心适用于 {50,25,10,5,1}。

那么问题来了：什么样的硬币面值满足贪心算法，可以使1到100之间的任何值所需的最小硬币数最少？答案很简单：有100个不同面值的硬币，分别为1到100。虽然这种方法需要每次进行硬币的线性搜索，而且铸造如此多的不同面额的硬币和跟踪它们带来的开销也是相当大的。

现在，如果我们想要主要减少面额种类数，其次再最小化由贪心算法产生的1到100任意值所需的硬币数量，那么具有2的幂次面额的硬币：{64、32、16、8、4、2、1} 可以使1到100之间的任何值需求的最大硬币数为6（比较小于10的7位二进制数中1的个数），但这需要使用7种面额的硬币。五种面额 {50、25、10、5、1} 的最坏情况是在V=94和V=99出现的8个硬币。3的幂次面额硬币{1、3、9、27、81} 只需要使用5种面额就能满足贪心算法，但其最坏情况是在62和80处需要8个硬币。最后，使用 {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。

- Pavlo

2

理论：

如果贪心算法总是针对给定的硬币集合产生最优解，则称该集合为规范。

以下是关于确定任意n个硬币集合是否规范的已知最佳算法测试 [O(n^3)]，简洁地陈述如下：

[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]，其中 ai 是 ci 的计数）

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

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

而 w_ij 是通过将其 j 号硬币加1并将其从 j+1 到 n 的所有硬币计数归零后，由 G(c_(i-1) - 1) 产生的硬币向量的计算值。

实现（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.")

- inordirection

0

我们需要重新表述这个问题...贪心算法的本质就是尝试使用提供的硬币面额来获得目标值。对贪心算法所做的任何更改都只会改变达到目标值的方式。它不考虑使用的最少硬币数量...换句话说，这个问题不存在安全的解决方法。更高面额的硬币可能会更快地产生目标值，但这并不是一个安全的选择。例如{50,47,51,2,9}获取100，贪心选择将是取最高面额的硬币以更快地达到100，即51+47+2。虽然它已经达到了100，但50+50也可以达到。

现在让我们拿{50,47,51,9}获取100为例。如果它贪心地选择了最高面额的硬币51，那么它还需要从集合中找到49。它不知道是否可能，但它仍然尝试着去达到100，但它不能。而且改变贪心选择只会改变达到100的方式。这些类型的问题会产生一组解决方案，并形成决策树分支的形式。

- Kaushik Sai Kalyan

-1

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

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

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

希望这能给你一些想法。

996 A - Hit the lottery https://codeforces.com/blog/entry/60217

- Sarfaraz

2

1 2 5 10 20 50 100怎么样？ - randomUser

-5

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

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...；这仅仅是任何数字的二进制表示。在某种意义上，进制之间的转换本身就是一种贪心算法。

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

- Noxville

这是一个有趣的链接，但它只证明了一个事实，即如果一组最大硬币为m且非贪婪，则必须存在某个小于等于2m的总和，使得贪婪和最优解给出不同数量的硬币。（换句话说，它表明只需查看少量总和就可以“注意到”非贪婪。）也许有一种方法可以从这个证明中推出在每个贪婪的硬币集合中，每个硬币都必须是下一个最大硬币的两倍或更大，但我看不出来。 - j_random_hacker

3

你提供的链接证明了与你所声称的不同的事情，而你所声称它证明的内容也是错误的：硬币组合 {25, 10, 1} 符合你所说的“至少是前一个硬币面值的两倍”条件，但对于总额为30的情况，贪心算法会给出25+51（6枚硬币）的结果，而最优解是310（3枚硬币）。-1。 - j_random_hacker

贪心算法确实提供了一个有效的答案（25 + 1 + 1 + 1 + 1 + 1），只是不是最有效的。 - Noxville

OP的问题明确表明他/她打算将“works”解释为“使用最少数量的硬币”。（顺便说一句，如果你规定硬币组合包括1美分硬币，那么任何选择硬币的方法只要不导致总额超过目标金额，都可以按照你的较低标准“使用任意数量的硬币产生正确的找零”，因此贪心法毫无用处。） - j_random_hacker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tanu Saxena · Accepted Answer

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

S是一个有限非空集合
l是S的子集族(独立子集)的非空集合, 满足如果B属于l, A是B的子集，则A也属于l
如果A属于l, B属于l, 且|A|小于|B|,那么存在一些元素x属于B-A使得A并{x}属于l

在硬币找零问题中， S是按价值从大到小排序的所有硬币组成的集合。我们需要用S中最少的硬币数量达到价值V。

在我们的情况下，l是一个包含所有子集的独立集，满足它们的价值之和<=V。

如果我们的集合是一个拟阵，那么我们的答案就是在l中不能再加入任何元素的最大集合A。

为了验证，我们观察是否满足拟阵的性质，在S={25,15,1}, V=30的情况下。现在有两个l中的子集: A={25}和B={15,15} 由于|A| < |B|，根据3的条件，我们可以找到x属于B-A，使得(A并{x})属于l。所以{25,15}应该属于l，但是这是一个矛盾，因为25+15>30。

因此，S不是拟阵，因此贪心算法无法在其上运行。