3

我对 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("\nChange 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

4

3 回答 3

8

首先，了解递归的基本思想是什么：

  • 如果我们不用递归就可以解决问题，解决它并返回解决方案。
  • 如果不能，则将问题简化为一个或多个较小的问题，递归解决每个较小的问题，并结合解决方案来解决较大的问题。

二、了解动态规划的基本思想是什么：

  • 递归解决方案通常会多次重新计算同一个问题；有时存储解决方案比重新计算解决方案更有效。

好吧，让我们来解决你的问题。

// 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);

好吧，这是最容易的部分。困难的部分是什么？好吧，如果有一个解决方案，那么要么是二，要么是五，或者是十，对吧？或者也许所有三个。那么让我们来了解一下。

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 的想法，您必须给予表扬。不这样做就是剽窃，如果你坚持下去，你会被一所体面的学校开除。

于 2019-02-15T23:01:51.697 回答
3

这将打印所有可能的组合

    static void Main()
    {
        List<int> coins = new List<int>();
        List<int> amounts = new List<int>() { 2, 5, 10 };
        //
        // Compute change for 21 cents.
        //
        Change(coins, amounts, 0, 0, 21);
    }

    static void Change(List<int> coins, List<int> amounts, int highest, int sum, int goal)
    {
        //
        // See if we are done.
        //
        if (sum == goal)
        {
            Display(coins, amounts);
            return;
        }
        //
        // See if we have too much.
        //
        if (sum > goal)
        {
            return;
        }
        //
        // Loop through amounts.
        //
        foreach (int value in amounts)
        {
            //
            // Only add higher or equal amounts.
            //
            if (value >= highest)
            {
                List<int> copy = new List<int>(coins);
                copy.Add(value);
                Change(copy, amounts, value, sum + value, goal);
            }
        }
    }

    static void Display(List<int> coins, List<int> amounts)
    {
        foreach (int amount in amounts)
        {
            int count = coins.Count(value => value == amount);
            Console.WriteLine("{0}: {1}",
                amount,
                count);
        }
        Console.WriteLine();
    }

如果您只想要最少的组合更改代码

static List<int> resultCoins = new List<int>();
    static void Main()
    {
        List<int> amounts = new List<int>() { 2, 5, 10 };
        Change(new List<int>(), amounts, 0, 0, 21);
        Display(resultCoins, amounts);
    }

    static void Change(List<int> coins, List<int> amounts, int highest, int sum, int goal)
    {
        if (sum == goal)
        {
            resultCoins = coins;
            return;
        }
        if (sum > goal)
        {
            return;
        }
        foreach (int value in amounts)
        {
            if (value >= highest)
            {
                List<int> copy = new List<int>(coins);
                copy.Add(value);
                Change(copy, amounts, value, sum + value, goal);
            }
        }
    }

    static void Display(List<int> coins, List<int> amounts)
    {
        foreach (int amount in amounts)
        {
            int count = coins.Count(value => value == amount);
            Console.WriteLine("{0}: {1}", amount, count);
        }
        Console.WriteLine();
    }

结果：

2: 3
5: 1
10: 1
于 2019-02-15T14:11:40.430 回答
2

您可以做的是创建一个方法来返回构成金额的面额。您可以通过循环查找小于或等于剩余金额的最大面额来做到这一点。你这样做，直到余额低于可用的最低面额（2 欧元）。像这样的东西：

public static IEnumerable<int> MakeChange(int amount)
{
    int[] denominations = {2, 5, 10};
    while (amount >= denominations.Min())
    {
        var denomination = denominations.Where(i => i <= amount).Max();
        amount -= denomination;
        yield return denomination;
    }
}

这将 - 对于 22 - 返回 10、10、2。然后您可以使用 LINQ GroupBy 方法将它们分组为面额并写出每个面额的计数，如下所示：

    foreach (var d in MakeChange(22).GroupBy(i => i))
    {
        Console.WriteLine(d.Key + " " + d.Count());
    }

那会打印

10 2
2 1

这意味着您需要两张 10 欧元的钞票和一枚 2 欧元的硬币才能兑换 22 欧元的零钱。

于 2019-02-15T11:55:22.953 回答