您好,我正在尝试创建一个算法,找出有多少种方法可以找回零钱。 但我就是无法正确实现,我一直在应该得到 6 的地方得到 4,我只是不明白为什么。
这是我在 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];
}
最佳答案
出于纯粹的深夜无聊(是的,这肯定需要改进)...它同时使用递归、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;
}
}
}
}
关于c# - 硬币变化,只是不能正确,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3928854/