如何使用递归在C#中获得硬币兑换问题的最小可能组合-C#/.NET问题

How to get the least possible combination for a coin change problem in C# using recursion(如何使用递归在C#中获得硬币兑换问题的最小可能组合)

本文介绍了如何使用递归在C#中获得硬币兑换问题的最小可能组合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我是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)。答案没有改变，但我们重新进行了计算。

那么，我们该怎么办？我们使用动态编程技术。有两种方法可以做到这一点：