Algorithme pour déterminer pièce de combinaisons

Cela semble un peu comme une Partition, sauf que vous n'utilisez pas tous les entiers de 1:50. Il semble également similaire à bin packing problème avec de légères différences:

• Wikipédia: Partition (Théorie Des Nombres)
• Wikipédia: Bin packing problème
• Wolfram Mathworld: Partitions

En fait, après réflexion, c'est un PAI, et donc NP-dur.

Je vous suggère de certains de programmation dynamique appyroach. Fondamentalement, vous souhaitez définir une valeur "reste" et réglez quel que soit votre objectif était de (50). Ensuite, à chaque étape, vous devrez faire les suivants:

1. Comprendre quelle est la plus grande pièce de monnaie qui peut tenir dans le reste
2. Demander ce qui se passera si vous (A) inclus cette pièce de monnaie ou (B) n'incluent pas cette pièce.
3. Pour chaque scénario, de manière récursive.

Donc si le reste était de 50, et la plus grande de pièces d'une valeur de 25 et 10, vous feriez branche dans deux scénarios:

1. Remainder = 25, Coinset = 1x25
2. Remainder = 50, Coinset = 0x25

L'étape suivante (pour chaque branche) comme:

1-1. Remainder = 0,  Coinset = 2x25 <-- Note: Remainder=0 => Logged
1-2. Remainder = 25, Coinset = 1x25
2-1. Remainder = 40, Coinset = 0x25, 1x10
2-2. Remainder = 50, Coinset = 0x25, 0x10

Chaque branche est divisée en deux branches, à moins que:

• le reste était de 0 (dans ce cas, vous auriez du journal)
• le reste a été inférieure à la plus petite pièce de monnaie (auquel cas vous devriez jeter)
• il n'y avait pas plus de pièces de monnaie à gauche (dans ce cas, vous jetteriez-il depuis le reste != 0)

OriginalL'auteur

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

OriginalL'auteur

Comme pour la deuxième partie de votre question, supposons que vous disposez de la chaîne dans le fichier coins.txt:

#include <fstream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::ifstream coins_file("coins.txt");
    std::vector<int> coins;
    std::copy(std::istream_iterator<int>(coins_file),
              std::istream_iterator<int>(),
              std::back_inserter(coins));
}

Maintenant le vecteur coins contiendra les possibles valeurs de pièces.

OriginalL'auteur

Plutôt muet démarche est la suivante. Vous construire une cartographie de la "pièce de monnaie dont la valeur X est utilisé Y fois" et puis énumérer toutes les combinaisons possibles et sélectionner uniquement ceux dont le total est la somme désirée. Évidemment, pour chaque valeur de X que vous devez vérifier, Y allant de 0 jusqu'à la somme désirée. Ce sera plutôt lent, mais permettra de résoudre votre tâche.

OriginalL'auteur

En gros, vous avez à résoudre l'équation suivante: 50 = a*4 + b*6 + c*10 + d*15, où les inconnues sont a,b,c,d. Vous pouvez calculer par exemple d = (50 - a*4 - b*6 - c*10)/15 et ainsi de suite pour chaque variable. Ensuite, vous commencez à donner d toutes les valeurs possibles (vous devez commencer par celle qui a le moins de valeurs possibles, ici, d): 0,1,2,3,4 et de commencer à donner à c toutes les valeurs possibles en fonction de la valeur actuelle de d et ainsi de suite.

OriginalL'auteur

Un algorithme est une procédure pour la résolution d'un problème, il n'a pas à être dans une langue donnée.

D'abord travailler sur les entrées:

typedef int CoinValue;

set<CoinValue> coinTypes;
int value;

et les sorties:

set< map<CoinValue, int> > results;

Résoudre pour le cas le plus simple que vous pouvez penser d'abord:

coinTypes = { 1 }; //only one type of coin worth 1 cent
value = 51;

le résultat devrait être:

results = { [1 : 51] }; //only one solution, 51 - 1 cent coins

Comment résoudriez-vous ci-dessus?

Comment à ce sujet:

coinTypes = { 2 };
value = 51;

results = { }; //there is no solution

quoi à ce sujet?

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.

OriginalL'auteur

Une autre version de Python:

def change(coins, money):
    return (
        change(coins[:-1], money) +
        change(coins, money - coins[-1])
        if money > 0 and coins
        else money == 0
    )

OriginalL'auteur