3

您好，我正在尝试创建一个算法来找出我可以通过多少种方式找回零钱。但我就是无法正确执行，我一直得到 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];
    }
4

5 回答 5

5

出于纯粹的深夜无聊（是的，这肯定需要改进）......它同时使用递归，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;
                }
            }
        }
    }
于 2010-10-14T00:42:06.890 回答
2

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

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

于 2010-10-14T04:35:17.183 回答
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同样。

于 2010-10-13T23:31:44.333 回答
1

我相信您的意思是 table[i, j] 仅使用硬币 {0, 1, 2,..., j - 1} 来存储达到 i 美分值的方法的数量。

本质上，while 循环的内部部分是说 table[i, j] 应该等于在不使用任何硬币 j 的情况下达到 i 值的方式数，加上使用 at 达到 i 值的方式数至少一枚价值 S[j] 的硬币。因此，除了边界情况，值为 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)。

于 2010-10-14T00:25:26.883 回答
1

一些观察。

count1）如果您将函数从伪代码移动到单独的子例程中，它将使您的代码更简单（并且不易出错） 。像这样的东西（基于您链接中的伪代码）

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

于 2010-10-13T23:37:46.780 回答