如何使用递归在C#中获得硬币兑换问题的最小可能组合 [英] How to get the least possible combination for a coin change problem in C# using recursion
问题描述
我是C#的新手，我有一个递归问题要解决。我想在这个硬币兑换问题中得到尽可能少的硬币。我已经调整了一个算法，但我需要返回一个类型为Change的对象，该对象将包含最小可能的组合。
我试图实现一个算法，但我有所有可能的组合。
using System;
using System.Collections.Generic;
using System.Linq;
// Do not modify change
class Change
{
public long coin2 = 0;
public long bill5 = 0;
public long bill10 = 0;
}
class Solution
{
// Do not modify method signature
public static Change OptimalChange(long s)
{
Change _change = new Change();
//To implement here
return _change;
}
public static int GetCombinations(int total, int index, int[] list, List<int> cur)
{
if (total == 0)
{
foreach (var i in cur)
{
Console.Write(i + " ");
}
Console.WriteLine();
return 1;
}
if (index == list.Length)
{
return 0;
}
int ret = 0;
for (; total >= 0; total -= list[index])
{
ret += GetCombinations(total, index + 1, list, cur);
cur.Add(list[index]);
}
for (int i = 0; i < cur.Count(); i++)
{
while (cur.Count > i && cur[i] == list[index])
{
cur.RemoveAt(i);
}
}
return ret;
}
}
public class Program
{
public static void Main()
{
Console.WriteLine("Hello Change");
int s = 41;
/*Change m = Solution.OptimalChange(s);
Console.WriteLine("Coins(s) 2euros :" + m.coin2);
Console.WriteLine("Bill(s) 5euors :" + m.bill5);
Console.WriteLine("Bill(s) 10euors :" + m.bill10);
long result = m.coin2*2 + m.bill5*5 + m.bill10*10;
Console.WriteLine("
Change given =", + result);*/
Solution sol = new Solution();
int[] l = {
2,
5,
10
};
Solution.GetCombinations(s, 0, l, new List<int>());
}
}
预期结果
示例：可用的硬币为{2，5，10}
--我的输入为12--
程序应返回
硬币2欧元：1 账单5份：0份 账单10个：1--我的输入为17--
程序应返回
硬币2欧元：1 比尔5个职位：1 账单10个：1推荐答案
首先，了解递归的基本思想是什么：
- 如果我们可以在不使用递归的情况下解决问题，则将其求解并返回解决方案。
- 如果不能，则将问题简化为一个或多个较小的问题，递归地解决每个较小的问题，然后组合解决方案以解决较大的问题。
第二，了解动态规划的基本思想：
- 递归解决方案通常会多次重新计算同一问题；存储解决方案有时比重新计算更有效。
好的，让我们来解决您的问题。
// Do not modify change
class Change
{
public long coin2 = 0;
public long bill5 = 0;
public long bill10 = 0;
}
sealed class Change
{
public long Two { get; }
public long Five { get; }
public long Ten { get; }
public Change(long two, long five, long ten)
{
this.Two = two;
this.Five = five;
this.Ten = ten;
}
public Change AddTwo() => new Change(Two + 1, Five, Ten);
public Change AddFive() => new Change(Two, Five + 1, Ten);
public Change AddTen() => new Change(Two, Five, Ten + 1);
public long Count => Two + Five + Ten;
public long Total => Two * 2 + Five * 5 + Ten * 10;
}
从帮助您而不是伤害您的数据结构开始。
现在，让我们编写一个递归函数：
public static Change OptimalChange(long s)
{
// Are we in the base case? Solve the problem.
// If not, break it down into a smaller problem.
}
基本情况是什么？实际上有两个。如果和为负，则没有解，如果和为零，则解为零。
public static Change OptimalChange(long s)
{
if (s < 0)
return null;
if (s == 0)
return new Change(0, 0, 0);
好了，这是最简单的部分。最难的是什么？嗯，如果有一个解决方案，那么它要么是2，要么是5，要么是10，对吧？或者三个都是。所以让我们来找出答案。
public static Change OptimalChange(long s)
{
if (s < 0)
return null;
if (s == 0)
return new Change(0, 0, 0);
Change tryTen = OptimalChange(s - 10)?.AddTen();
...
你能把它从这里带走吗？
了解当您拥有实现所需操作的数据结构时，问题会变得多么简单？同样，始终创建有助于您的数据结构。
下一个问题：此算法效率非常低。为什么？因为我们在不断地重新做我们已经做过的问题。假设我们正在评估OptimalChange(22)。它调用OptimalChange(12)，后者调用OptimalChange(7)，后者调用OptimalChange(5)。但OptionalChange(12)也调用OptimalChange(10)，后者再次调用OptimalChange(5)。答案没有改变，但我们重新进行了计算。
那么，我们该怎么办？我们使用动态编程技术。有两种方法可以做到这一点：
- 继续递归，并记住递归函数。
- 创建一个更改数组，并根据需要填写它。
但请稍等，还有比性能问题更多的问题。我们使问题变小，每次最大值为10，最小值为2，但参数很长；可能是数十亿或万亿。如果我们有一个递归解决方案，我们就会打乱堆栈，如果我们有一个基于数组的解决方案，它就太大了。
我们需要更聪明地在给定的可能输入范围内解决此问题。好好想想；我们能不能在没有递归、数组或长时间循环的情况下解析地解决这个问题？或者，同样地，有没有办法将极大的问题迅速减少为小问题？然后，这个小问题就可以用动态规划解决了。
像家庭作业问题一样记住，你是受优秀学术规则的约束。如果您在作业解决方案中使用了来自SO的想法，您必须给予信任。不这样做是抄袭，如果你继续这样做，你会被一所像样的学校开除。
这篇关于如何使用递归在C#中获得硬币兑换问题的最小可能组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
