硬币找零问题，我就是做不对

Question

你好，我正在尝试创建一个算法来找出可以获得多少种零钱的方法。

但是，我无法正确地实现它，我的答案一直是4，而不是6，我真的不知道为什么。

这是我的C#实现，它是根据http://www.algorithmist.com/index.php/Coin_Change上的伪代码创建的。

     private static int[] S = { 1, 2, 5 };
        private static void Main(string[] args)
        {
            int amount = 7;
            int ways = count2(amount, S.Length);
            Console.WriteLine("Ways to make change for " + amount + " kr: " + ways.ToString());
            Console.ReadLine();
        }    
static int count2(int n, int m)
        {
        int[,] table = new int[n,m];

        for (int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                // Rules
                // 1: table[0,0] or table[0,x] = 1
                // 2: talbe[i <= -1, x] = 0
                // 3: table[x, j <= -1] = 0

                int total = 0;

                // first sub-problem
                // count(n, m-1)
                if (i == 0) // rule 1
                    total += 1;
                else if (i <= -1) // rule 2
                    total += 0;
                else if (j - 1 <= -1)
                    total += 0;
                else
                    total += table[i, j-1];

                // second sub-problem
                // count(n-S[m], m)
                if (j - 1 <= -1) // rule 3
                    total += 0;
                else if (i - S[j - 1] == 0) // rule 1
                    total += 1;
                else if (i - S[j - 1] <= -1) // rule 2
                    total += 0;
                else
                    total += table[i - S[j-1], j];

                table[i, j] = total;
            }
        }
        return table[n-1, m-1];
    }

- Androme

---

抱歉，它应该是0..n和0..m。 - Androme

Answer 1

由于深夜无聊，我写了下面这段代码（当然，这需要加以改进）……它同时使用了递归、linq和yield，并且每行代码都有很多括号，所以我对它感到非常满意。

    static IEnumerable<List<int>> GetChange(int target, IQueryable<int> coins)
    {
        var availableCoins = from c in coins where c <= target select c;
        if (!availableCoins.Any())
        {
            yield return new List<int>();
        }
        else
        {
            foreach (var thisCoin in availableCoins)
            {
                foreach (var result in GetChange(target - thisCoin, from c in availableCoins where c <= thisCoin select c))
                {
                    result.Add(thisCoin);
                    yield return result;
                }
            }
        }
    }

- Dan Puzey

---

这是非常简洁明了的，你说的对，同时使用了各种技巧。但是，如果给定硬币没有解决方案，则计算最接近的更小零钱的解决方案。例如，目标20，硬币3、6会产生总和为18的组合。因此，只需要检查结果是否加起来等于目标即可使用此方法。 - goodeye

实际上，由于这个循环遍历了所有的硬币直到目标值，因此它包含了正确和不正确的解决方案。例如，使用6和5凑出18元会得到666、566、556和555等结果。 - goodeye

Answer 2

如果您能解释一下算法的工作原理将非常有用。当没有注释并且变量只被命名为n，m，i时，很难理解其目的。例如，在迭代各种类型的硬币时，应该使用更多描述性的名称，如coinType。

然而，有一些地方看起来非常可疑。例如，您的变量i和j在范围1..m或1..n内迭代 - 它们始终是正数。这意味着您的规则2和3永远不会运行：

// ...
  else if (i <= -1)     // <- can never be 'true'
    total += 0; 
  else if (j - 1 <= -1) // <- 'true' when 'j == 0'
// ...
  if (j - 1 <= -1)      // <- can never be 'true'
// ...

i 永远不会小于或等于 -1，同样的，j 也是如此。

- Tomas Petricek

---

抱歉，应该是0..n和0..m :D - Androme

@DoomStone：即使i可能是0，i <= -1也永远不会发生。如果条件只处理一些特殊情况（单个元素），那么你可以写成if (i == 0) ...以增加可读性。 - Tomas Petricek

这是正确的，但它不应该对结果产生影响。 - Androme

@DoomStone：是的，它们意思相同，但后者更容易理解。我仍然不理解你代码背后的逻辑，我相信像这样的小改动（重命名和添加一些注释）会真正有所帮助。 - Tomas Petricek

Answer 3

以下是算法的运行顺序。点击绿色“播放”箭头以运行它。 http://www.exorithm.com/algorithm/view/make_change

我认为主要问题在于算法循环应该从-1开始。我认为递归写起来会更清晰，但这是一个有趣的练习。

- Mike C

Answer 4

一些观察。

1）如果您将伪代码中的 count 函数移入单独的子例程中，会使您的代码更简单（且错误更少）。类似这样（基于您链接中的伪代码）

func count(table, i, j)
  if ( i == 0 ) 
    return 1
  if ( i < 0 )
    return 0
  if ( j <= 0 and i >= 1 )
    return 0

  return table[i][j]
end

然后你可以这样做

table[i][j] = count(table, i, j - 1) + count(table, i - S[j], j)

在你的内部循环中。

2) 在 count2 中，你的第一个循环将会执行 n - 1 次。这意味着，当 n == 1 时，你不会进入循环体，也不会找到任何解决方案。对于内部循环也是一样的：如果只有一个硬币，你也找不到任何解决方案。

- Nikita Rybak

---

我给你的代码有一个错误，应该是0到n和0到m。我已经在第一篇帖子中修复了代码。 - Androme

@DoomStone 不想显得卖弄，但我真的认为在你的内部循环中消除“意大利面条式代码”将有助于找到错误。 - Nikita Rybak

Answer 5

我相信你的意思是让table[i, j]存储使用硬币{0, 1, 2,..., j - 1}，恰好凑出i分钱的方法数。

实际上，while循环的内部部分表明，table[i, j]应该等于不使用硬币j时达到价值i的方法数，加上至少使用一枚面值为S[j]的硬币达到价值i的方法数。因此，除了边界情况外，该值为table[i, j - 1] + table[i - S[j], j]；和式的第一部分是不使用面值为S[j]的硬币达到i的方法数，第二部分是使用至少一枚面值为S[j]的硬币达到i的方法数。

尝试更改：

        // second sub-problem
        // count(n-S[m], m)
        if (j - 1 <= -1) // rule 3
            total += 0;
        else if (i - S[j - 1] == 0) // rule 1
            total += 1;
        else if (i - S[j - 1] <= -1) // rule 2
            total += 0;
        else
            total += table[i - S[j-1], j];

至：

        // second sub-problem
        // count(n-S[m], m)
        if (i - S[j] == 0) // rule 1
            total += 1;
        else if (i - S[j] < 0) // rule 2
            total += 0;
        else
            total += table[i - S[j], j];

顺便提一下，通常写法是 (j < 0) 而不是 (j <= -1)。

- jonderry

---

如果我将if (j - 1 <= -1)更改为if(j <= -1)，它会导致越界错误吗？ - Androme

应该是 s[j-1]，因为 S 从0开始到m-1。 - Androme

我认为你不需要那个测试。看看修改后的代码。变量j永远不会小于0。 - jonderry

是的，在每个 i 循环时，j 都将为 0，然后 j-1 = -1。 - Androme

这就是为什么你需要将 j - 1 改为 j。 - jonderry