Trouvez le plus petit nombre de pièces nécessaires pour rendre n'importe quelle monnaie de 1 à 99 cents.

Question

Récemment, j'ai mis mon collègue au défi d'écrire un algorithme pour résoudre ce problème :

Trouvez le plus petit nombre de pièces nécessaires pour rendre n'importe quelle monnaie de 1 à 99 cents. Les pièces ne peuvent être que des pennies (1), des nickels (5), des dimes (10) et des quarters (25), et vous devez être capable de rendre toutes les valeurs de 1 à 99 (par incréments de 1 cent) avec ces pièces.

Cependant, je me suis rendu compte que je ne sais pas vraiment comment le faire moi-même sans examiner toutes les combinaisons possibles de pièces. Il doit y avoir une meilleure façon de résoudre ce problème, mais je ne connais pas le nom générique de ce type d'algorithme et je n'arrive pas à trouver un moyen de le simplifier au-delà de l'examen de toutes les solutions.

Je me demandais si quelqu'un pouvait m'indiquer la bonne direction ou me proposer un algorithme plus efficace.

Answer 1

Ce que vous cherchez, c'est Programmation dynamique .

En fait, il n'est pas nécessaire d'énumérer toutes les combinaisons possibles pour toutes les valeurs possibles, car vous pouvez les construire par-dessus les réponses précédentes.

Votre algorithme doit prendre 2 paramètres :

• La liste des valeurs possibles des pièces, ici [1, 5, 10, 25]
• La gamme à couvrir, ici [1, 99]

Et le but est de calculer l'ensemble minimal de pièces nécessaires pour cette gamme.

La méthode la plus simple consiste à procéder de manière ascendante :

Range     Number of coins (in the minimal set)
          1   5   10   25
[1,1]     1
[1,2]     2
[1,3]     3
[1,4]     4
[1,5]     5
[1,5]*    4   1             * two solutions here
[1,6]     4   1
[1,9]     4   1
[1,10]    5   1             * experience tells us it's not the most viable one :p
[1,10]    4   2             * not so viable either
[1,10]    4   1   1
[1,11]    4   1   1
[1,19]    4   1   1
[1,20]    5   1   1         * not viable (in the long run)
[1,20]    4   2   1         * not viable (in the long run)
[1,20]    4   1   2

C'est assez facile, à chaque étape nous pouvons procéder en ajoutant au plus une pièce, nous devons juste savoir où. Cela se résume au fait que l'intervalle [x,y] est inclus dans [x,y+1] donc l'ensemble minimal pour [x,y+1] devrait inclure l'ensemble minimal pour [x,y] .

Comme vous l'avez peut-être remarqué, il y a parfois des indécisions, c'est-à-dire que plusieurs séries ont le même nombre de pièces. Dans ce cas, ce n'est que plus tard que l'on peut décider laquelle doit être éliminée.

Il devrait être possible d'améliorer son temps de fonctionnement, en remarquant que l'ajout d'une pièce permet généralement de couvrir une plage bien plus grande que celle pour laquelle vous l'avez ajoutée, je pense.

Par exemple, notez que :

 [1,5]    4*1  1*5
 [1,9]    4*1  1*5

nous ajoutons une pièce de 5 cents pour couvrir [1,5] mais cela nous donne jusqu'à [1,9] gratuitement !

Cependant, lorsqu'il s'agit d'ensembles d'entrées scandaleuses [2,3,5,10,25] pour couvrir [2,99] Je ne sais pas comment vérifier rapidement l'étendue de la couverture du nouvel ensemble ou si cela serait plus efficace.

Answer 2

Vous pouvez très rapidement trouver une limite supérieure.

Disons que vous prenez trois quarts. Il ne vous reste plus qu'à remplir les "trous" 1-24, 26-49, 51-74, 76-99 avec d'autres pièces.

De manière triviale, cela fonctionnerait avec 2 pièces de 10 cents, 1 pièce de 5 cents et 4 pièces de 10 cents.

Ainsi, 3 + 4 + 2 + 1 devrait être une limite supérieure pour votre nombre de pièces. Dès que votre algorithme de force brute dépasse cette limite, vous pouvez instantanément arrêter de chercher plus profondément.

Le reste de la recherche devrait être assez rapide pour n'importe quel usage de la programmation dynamique.

(edit : réponse corrigée selon l'observation de Gabe)

Answer 3

Vous avez besoin d'au moins 4 pennies, puisque vous voulez obtenir 4 comme monnaie, et vous ne pouvez le faire qu'avec des pennies.

Il n'est pas optimal d'avoir plus de 4 pennies. Au lieu de 4+x pennies, vous pouvez avoir 4 pennies et x nickels - ils couvrent au moins la même plage.

Donc vous avez exactement 4 pennies.

Vous avez besoin d'au moins 1 nickel, puisque vous voulez obtenir 5 comme monnaie.

Il n'est pas optimal d'avoir plus d'un nickel. Au lieu de 1+x pièces de 5 cents, vous pouvez avoir 1 pièce de 5 cents et x pièces de 10 cents - ils couvrent au moins la même gamme.

Donc vous avez exactement 1 nickel.

Il vous faut au moins 2 pièces de 10 cents, puisque vous voulez obtenir 20.

Cela signifie que vous avez 4 pennies, 1 nickel et au moins 2 dimes.

Si vous aviez moins de 10 pièces, vous auriez moins de 3 pièces. Mais alors, la monnaie maximale possible que vous pourriez obtenir en utilisant toutes les pièces est de 4 + 5 + 20 + 50 = 79, ce qui n'est pas suffisant.

Cela signifie que vous avez au moins 10 pièces. La réponse de Thomas montre qu'en fait, si vous avez 4 pennies, 1 nickel, 2 dimes et 3 quarters, tout va bien.

Answer 4

J'ai appris à connaître programmation dynamique aujourd'hui, et voici le résultat :

coins = [1,5,10,25]
d = {} # stores tuples of the form (# of coins, [coin list])

# finds the minimum # of coins needed to
# make change for some number of cents
def m(cents):
    if cents in d.keys():
        return d[cents]
    elif cents > 0:
        choices = [(m(cents - x)[0] + 1, m(cents - x)[1] + [x]) for x in coins if cents >= x]

        # given a list of tuples, python's min function
        # uses the first element of each tuple for comparison
        d[cents] = min(choices)
        return d[cents]
    else:
        d[0] = (0, [])
        return d[0]

for x in range(1, 100):
    val = m(x)
    print x, "cents requires", val[0], "coins:", val[1]

La programmation dynamique est vraiment magique.

Answer 5

Bonne question. Voici la logique à laquelle j'ai abouti. Je l'ai testée avec quelques scénarios, dont 25.

class Program
{

    //Allowable denominations
    const int penny = 1;
    const int nickel = 5;
    const int dime = 10;
    const int quarter = 25;

    const int maxCurrencyLevelForTest =55; //1-n where n<=99

    static void Main(string[] args)
    {         
        int minPenniesNeeded = 0;
        int minNickelsNeeded = 0; 
        int minDimesNeeded = 0; 
        int minQuartersNeeded = 0;

        if (maxCurrencyLevelForTest == penny)
        {
            minPenniesNeeded = 1;
        }
        else if (maxCurrencyLevelForTest < nickel)
        {
            minPenniesNeeded = MinCountNeeded(penny, maxCurrencyLevelForTest);                
        }
        else if (maxCurrencyLevelForTest < dime)
        {
            minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
            minNickelsNeeded = MinCountNeeded(nickel, maxCurrencyLevelForTest);                
        }
        else if (maxCurrencyLevelForTest < quarter)
        {
            minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
            minNickelsNeeded = MinCountNeeded(nickel, dime - 1);
            minDimesNeeded = MinCountNeeded(dime, maxCurrencyLevelForTest);
        }
        else
        {
            minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
            minNickelsNeeded = MinCountNeeded(nickel, dime - 1);
            minDimesNeeded = MinCountNeeded(dime, quarter - 1);

            var maxPossilbleValueWithoutQuarters = (minPenniesNeeded * penny + minNickelsNeeded * nickel + minDimesNeeded * dime);
            if (maxCurrencyLevelForTest > maxPossilbleValueWithoutQuarters)
            {               
                minQuartersNeeded = (((maxCurrencyLevelForTest - maxPossilbleValueWithoutQuarters)-1) / quarter) + 1;
            }
        }

        var minCoinsNeeded = minPenniesNeeded + minNickelsNeeded+minDimesNeeded+minQuartersNeeded;

        Console.WriteLine(String.Format("Min Number of coins needed: {0}", minCoinsNeeded));
        Console.WriteLine(String.Format("Penny: {0} needed", minPenniesNeeded));
        Console.WriteLine(String.Format("Nickels: {0} needed", minNickelsNeeded));
        Console.WriteLine(String.Format("Dimes: {0} needed", minDimesNeeded));
        Console.WriteLine(String.Format("Quarters: {0} needed", minQuartersNeeded));
        Console.ReadLine();
    }

    private static int MinCountNeeded(int denomination, int upperRange)
    {
        int remainder;
        return System.Math.DivRem(upperRange, denomination,out remainder);
    }
}

Quelques résultats : Lorsque maxCurrencyLevelForTest = 25

Min Number of coins needed: 7
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 0 needed

Lorsque maxCurrencyLevelForTest = 99

Min Number of coins needed: 10
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 3 needed

maxCurrencyLevelForTest : 54

Min Number of coins needed: 8
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 1 needed

maxCurrencyLevelForTest : 55

Min Number of coins needed: 9
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 2 needed

maxCurrencyLevelForTest : 79

Min Number of coins needed: 9
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 2 needed

maxCurrencyLevelForTest : 85

Min Number of coins needed: 10
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 3 needed

Le code peut encore être remanié, je suppose.