Algorithme pour déterminer les combinaisons de pièces

Pour un tel nombre de pièces de monnaie, vous pouvez écrire une solution de force brute simple.

Quelque chose comme ceci: xxx

une solution de force brute très sale qui imprime tout Combinaisons possibles.

C'est un problème très célèbre, essayez donc de lire des solutions meilleures que d'autres ont fourni.

Un algorithme est une procédure de résolution d'un problème, il n'est pas nécessaire que ce soit dans une langue particulière.

Premier éloigne les entrées: p> xxx pré>

et les sorties: p> xxx pré>

résolvez pour le cas le plus simple que vous pouvez Pensez à d'abord: p> xxx pré>

Le résultat doit être: p> xxx pré>

Comment résoudriez-vous ce qui précède? P>

Que diriez-vous: P>

coinTypes = { 1, 2 };
value = { 4 };

results = { [2: 2], [2: 1, 1: 2], [1: 4] }; // the order I put the solutions in is a hint to how to do the algorithm.

Si vous avez des pièces de 15, 10, 6 et 2 centimes et vous devez trouver combien de manières distinctes sont là pour arriver à 50 que vous pouvez

• comptez le nombre de moyens distincts que vous devez atteindre 50 en utilisant seulement 10, 6 et 2
• comptez combien de façons distincts vous devez atteindre 50-15 en utilisant seulement 10, 6 et 2
• comptez le nombre de moyens distincts que vous devez atteindre 50-15 * 2 en utilisant seulement 10, 6 et 2
• comptez combien de moyens distincts vous devez atteindre 50-15 * 3 en utilisant seulement 10, 6 et 2
• résumer tous ces résultats qui sont bien sûr distincts (dans la première fois, je n'ai utilisé aucune pièce de monnaie 15C, dans la seconde que j'utilisais un, dans les deux troisièmes et au quatrième trois).

  Pour que vous puissiez fondamentalement diviser le problème en des problèmes plus petits (montant éventuellement plus faible et moins de pièces de monnaie). Lorsque vous n'avez qu'un seul type de monnaie, la réponse est bien sûr triviale (vous ne pouvez pas atteindre le montant prescrit exactement ou vous pouvez dans la seule manière possible).

  En outre, vous pouvez également éviter de répéter le même calcul en utilisant Mémoisation, par exemple, le nombre de manières d'atteindre 20 en utilisant uniquement [6, 2] ne dépend pas si les 30 déjà payés ont été atteints à l'aide de 15 + 15 ou 10 + 10 + 10, de sorte que le résultat du faible problème (20 , [6, 2]) peut être stocké et réutilisé.

  en Python La mise en œuvre de cette idée est la suivante xxx

Voici une solution récursive en Java:

// Usage: int[] denoms = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 };       
// System.out.println(ways(denoms, denoms.length, 200));
public static int ways(int denoms[], int index, int capacity) {
    if (capacity == 0) return 1;
    if (capacity < 0 || index <= 0 ) return 0;
    int withoutItem = ways(denoms, index - 1, capacity); 
    int withItem = ways(denoms, index, capacity - denoms[index - 1]); 
    return withoutItem + withItem;
}

solution récursive basée sur algorithmist.com ressource dans SCALA:

def countChange(money: Int, coins: List[Int]): Int = {
    if (money < 0 || coins.isEmpty) 0
    else if (money == 0) 1
    else countChange(money, coins.tail) + countChange(money - coins.head, coins)
}

Une autre version Python: xxx