代码之家 › 专栏 › 技术社区 › Androme

换硬币,就是找不到对的。

coin-change algorithm c#

Androme · 技术社区 · 15 年前

你好,我正在尝试创建一个Algorythm,它可以找出多少方法可以让我找回零钱。但我不能正确地理解,我总是得到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];
    }

5 回复 | 直到 13 年前

Mike C 15 年前

这是算法的工作顺序。按绿色的“播放”箭头运行。 http://www.exorithm.com/algorithm/view/make_change

我认为主要的问题是算法循环应该从-1开始。我认为它会更清楚地递归地写,但这是一个有趣的练习。

Dan Puzey 15 年前

出于纯粹的深夜无聊(是的,这肯定需要改进)。它同时使用递归、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;
                }
            }
        }
    }

Tomas Petricek 15 年前

如果你解释一下你的算法是如何工作的,这将是很有用的。当没有注释和变量的命名只是 n , m , i 很难理解目的。您应该使用更具描述性的名称,例如 coinType 例如,在不同类型的硬币上迭代时。

然而,有些地方对我来说很可疑。例如,您的变量 我 和 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'
// ...

我 永远不会小于或等于 -1 和 J 同样地。

Nikita Rybak 15 年前

一些观察结果。

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 您不会进入循环体,也不会找到任何解决方案。内环也一样:如果只有一枚硬币,你就找不到任何解决办法。

jonderry 15 年前

我相信你的意思是,对于表[i,j]来说,只使用硬币0,1,2,…,j-1来存储达到精确1美分价值的方法的数量。

本质上,while循环的内部部分表示表[i,j]应等于在不使用任何硬币j的情况下达到i值的方法数,加上至少使用一枚硬币s[j]达到i值的方法数。因此,除边界情况外,该值为表[I,J-1]+表[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)。