Как получить наименьшую возможную комбинацию для проблемы смены монет в C # с помощью рекурсии

Question

Я довольно новичок в 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

Answer 1

При этом будут напечатаны все возможные комбинации

    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

Answer 2

Прежде всего, поймите, какова основная идея рекурсии:

• Если мы можем решить проблему без рекурсии, решите ее и верните решение.
• Если мы не можем,затем сведите проблему к одной или нескольким более мелким задачам, рекурсивно решите каждую более мелкую проблему и объедините решения для решения более крупной проблемы.

Во-вторых, поймите, какова основная идея динамического программирования:

• Рекурсивные решения часто повторно вычисляют одну и ту же проблему много раз;иногда более эффективно хранить решение, а не пересчитывать его.

Хорошо, давайте приступим к вашей проблеме.

// Do not modify change
class Change
{
    public long coin2 = 0;
    public long bill5 = 0;
    public long bill10 = 0;
}

Pish tosh.Этот класс ужасен .Исправьте это!

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 в своих решениях для домашних заданий, вы должны дать кредит .Невыполнение этого требования - плагиат, из-за которого вас исключат из приличной школы.

Answer 3

Что вы могли бы сделать, это сделать метод, который возвращает номиналы, которые составляют сумму.Вы можете сделать это, зацикливаясь и найти наибольшую номинальную стоимость, которая меньше или равна оставшейся части суммы.Вы делаете это до тех пор, пока остаток не станет ниже минимально возможного номинала (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 евро в обмен.