为什么贪婪硬币找零算法对某些套币的工作？ [英] Why does the greedy coin change algorithm not work for some coin sets?

问题描述

我明白是怎么贪心算法硬币找零问题（支付的具体数额硬币的最小可能的数量）的作品 - 它总是选择具有最大面额不超过余额的硬币 - 并且它总能找到的正确的解决方案，为特定的套币。

I understand how the greedy algorithm for the coin change problem (pay a specific amount with the minimal possible number of coins) works - it always selects the coin with the largest denomination not exceeding the remaining sum - and that it always finds the correct solution for specific coin sets.

但对于一些套币，还有为其贪心算法失败款项。例如，对于该组 {1，15，25} 和的总和30，贪心算法首先选择25，留下的5剩余部分，​​然后5 1秒为一个总共六个硬币。但硬币的最小数量的解决方案是选择15次。

But for some coin sets, there are sums for which the greedy algorithm fails. For example, for the set {1, 15, 25} and the sum 30, the greedy algorithm first chooses 25, leaving a remainder of 5, and then five 1s for a total of six coins. But the solution with the minimal number of coins is to choose 15 twice.

什么样的​​条件必须一套硬币履行这样贪心算法找到的所有款项最小的解决方案？

What conditions must a set of coins fulfil so that the greedy algorithm finds the minimal solution for all sums?

推荐答案

一组形成一个拟阵（的https：// EN。 wikipedia.org/wiki/Matroid 的）可被用来解决的硬币通过使用贪婪方法改变的问题。简言之，拟阵是一个有序对 M =（S，L）满足以下条件：

A set which forms a matroid (https://en.wikipedia.org/wiki/Matroid) can be used to solve the coin changing problem by using greedy approach. In brief, a matroid is an ordered pair M = (S,l) satisfying the following conditions:

1. S是一个有限非空集
2. →是S的子集的非空的家庭，被称为独立的子集，所以如果B->→ 和A是B的一个子集，则A - >→
3. 如果A->升，B->升和| A | ＆LT; | B |，再有就是一些元素的x> BA，使得非盟{X} - >→

1. S is a finite nonempty set
2. l is a nonempty family of subsets of S, called the independent subsets,such that if B->l and A is a subset of B, then A -> l
3. If A-> l, B-> l and |A| < |B|, then there is some element x-> B-A such that A U {x} ->l

在我们的硬币变化的问题​​，S是递减的顺序值集中的所有硬币 我们需要通过硬币中的最低数量实现V的值

In our question of coin changing, S is a set of all the coins in decreasing order value We need to achieve a value of V by minimum number of coins in S

在我们的情况下，l是一个独立的集包含所有，使得下式成立的每个子集中的子集：中值的它们的总和为＆lt; = V

In our case, l is an independent set containing all the subsets such that the following holds for each subset: the summation of the values in them is <=V

如果我们的设置是一个拟阵，那么我们的答案是最大的集合A中升，其中的NO x，还可以加入

If our set is a matroid, then our answer is the maximal set A in l, in which no x can be further added

要检查，我们看到如果拟阵保持在设定的属性S = {25,15,1}，其中V = 30 现在，有在升两个子集： A = {25}和B = {15,15} 由于| A | ＆LT; | B |，再有就是一些元素的x> BA，使得非盟{X} - > L（据3） 因此，{25,15}应该属于升，但它的一对矛盾，因为25 + 15> 30

To check, we see if the properties of matroid hold in the set S = {25,15,1} where V = 30 Now, there are two subsets in l: A = {25} and B= {15,15} Since |A| < |B|, then there is some element x-> B-A such that A U {x} ->l (According 3) So, {25,15} should belong to l, but its a contradiction since 25+15>30

所以，S是不是一个拟阵，因此贪婪的做法将不会进行这项工作。

So, S is not a matroid and hence greedy approach won't work on it.

这篇关于为什么贪婪硬币找零算法对某些套币的工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！