Comment obtenir le moins de combinaison possible pour un problème de changement de pièce en C # en utilisant la récursivité

Ce que vous pourriez faire, c'est créer une méthode qui renvoie les dénominations qui constitueraient le montant. Vous pouvez le faire en faisant une boucle et trouver la plus grande dénomination inférieure ou égale au reste du montant. Vous faites cela jusqu'à ce que le reste soit inférieur à la valeur la plus basse disponible (2 euros). Quelque chose comme ceci:

10 2
2 1

Cela - pour 22 - renvoie 10, 10, 2. Vous pouvez ensuite utiliser la méthode LINQ GroupBy pour les regrouper en dénominations et écrire le décompte de chacune comme ceci :

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

Cela imprimerait

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;
    }
}

Cela signifie que vous auriez besoin de deux billets de 10 euros et d'une pièce de 2 euros pour faire 22 euros de monnaie.

Ceci imprimera toutes les combinaisons possibles

2: 3
5: 1
10: 1

Si vous ne voulez que la moindre combinaison, changez le code pour ceci

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();
    }

Résultat: p>

    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();
    }

Tout d'abord, comprenez quelle est l'idée de base de la récursivité:

• Si nous pouvons résoudre le problème sans récursivité, résolvez-le et renvoyez la solution.
• Si nous ne pouvons pas, réduisez le problème à un ou plusieurs problèmes plus petits, résolvez chaque problème plus petit de manière récursive et combinez les solutions pour résoudre le problème plus grand.

Deuxièmement, comprenez quelle est l'idée de base de la programmation dynamique:

• Les solutions récursives recalculent souvent le même problème plusieurs fois; il est parfois plus efficace de stocker la solution que de la recalculer.

Très bien, attaquons votre problème.

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();
    ...

Pish tosh. Ce cours est terrible . Corrigez-le!

public static Change OptimalChange(long s)
{
    if (s < 0) 
      return null;
    if (s == 0) 
      return new Change(0, 0, 0);

Commencez avec une structure de données qui vous aide, pas une structure qui vous fait mal .

Maintenant, allons écrire une fonction récursive:

public static Change OptimalChange(long s)
{
    // Are we in the base case? Solve the problem.
    // If not, break it down into a smaller problem.
}

Quel est le cas de base? Il y en a en fait deux. Si la somme est négative, il n'y a pas de solution , et si la somme est nulle, alors il y a une solution nulle .

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;
}

Très bien, c'est la partie la plus facile. Quelle est la partie la plus difficile? Eh bien, s'il y a une solution, alors soit il a un deux, soit il a un cinq, soit il a un dix, non? Ou peut-être les trois. Voyons donc.

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

Pouvez-vous partir d'ici?

Voyez à quel point le problème devient plus simple lorsque vous avez une structure de données qui implémente les opérations dont vous avez besoin? Encore une fois créez toujours une structure de données qui vous aide .

Problème suivant: Cet algorithme est très inefficace . Pourquoi? Parce que nous refaisons constamment les problèmes que nous avons déjà posés. Supposons que nous évaluions OptimalChange (22). Cela appelle OptimalChange (12), qui appelle OptimalChange (7), qui appelle OptimalChange (5). Mais OptionalChange (12) appelle également OptimalChange (10), qui appelle à nouveau OptimalChange (5). La réponse n'a pas changé, mais nous refaisons le calcul.

Alors, que faisons-nous? Nous utilisons une technique de programmation dynamique . Il existe deux façons de procéder:

• Continuez à être récursif et mémorisez la fonction récursive.
• Créez un tableau de modifications et remplissez-le au fur et à mesure.

Mais attendez, il y a plus de problèmes que de problèmes de performances. Nous réduisons le problème d'un maximum de 10 et d'un minimum de 2 à chaque fois, mais le paramètre est long; cela pourrait être des milliards ou des billions. Si nous avons une solution récursive, nous allons faire exploser la pile, et si nous avons une solution basée sur un tableau, elle est trop grande.

Nous devons être plus intelligents pour résoudre ce problème sur le gamme d'entrées possibles . Pensez-y bien; Pouvons-nous résoudre le problème de manière analytique, sans récursivité, sans tableaux ni boucles de longue durée ? Ou, de manière équivalente, existe-t-il un moyen de réduire rapidement les problèmes extrêmement importants en petits problèmes ? Le petit problème peut alors être résolu avec la programmation dynamique.

Comme c'est toujours le cas avec les problèmes de devoirs rappelez-vous que vous êtes lié par les règles de la bonne recherche . Si vous utilisez des idées de SO dans vos solutions de devoirs, vous devez donner du crédit . Ne pas le faire est du plagiat et vous fera expulser d'une école décente si vous continuez.