Qu'est-ce qu'un bon algorithme pour décider si une quantité transmise peut être construite additivement à partir d'un ensemble de nombres?

Question

Possible en double:
Algorithm to find which numbers from a list of size n sum to another number

Qu'est-ce qu'un bon algorithme pour décider si un passé dans le montant peut être construit à partir d'un additivement ensemble de nombres. Dans mon cas, je suis en train de déterminer si un certain montant en devise (tel que 40 $) peut être atteint en additionnant une combinaison d'un ensemble de factures (comme des billets de 5 $, 10 $ et 20 $). C'est un exemple simple, mais l'algorithme doit fonctionner pour le cas générique où l'ensemble de factures peut différer au fil du temps (en raison de l'épuisement d'une facture) ou en raison de dénominations de billets différant par la monnaie. Le problème s'appliquerait à un caissier de change dans un aéroport.

Donc 50 $ peut être atteint avec un ensemble de (20 $ et 30 $), mais ne peut être atteint avec un ensemble de (20 $ et 40 $).

En outre. Si le montant ne peut pas être atteint avec les coupures de billets disponibles, comment déterminez-vous les montants les plus proches au-dessus et au-dessous desquels vous pouvez répondre?

Answer 1

Une réponse similaire a été donnée ici: Algorithm to find which numbers from a list of size n sum to another number

Answer 2

Vous recherchez le problème de changement de pièce:

• http://en.wikipedia.org/wiki/Coin_problem

• http://www.egr.unlv.edu/~jjtse/CS477/DP%20Coin%20Change.html

• http://www.algorithmist.com/index.php/Coin_Change

Answer 3

Commencez avec les plus grands projets de loi et de travailler vers le bas. Commencez avec le plus grand nombre de ces factures et travaillez avec chaque dénomination. Vous pourriez avoir besoin de moins d'une grande dénomination parce que vous avez besoin de plusieurs plus petits pour frapper une valeur sur la tête.

Answer 4

Cela semble étroitement lié au problème de somme de sous-ensemble, qui est NP-complet en général.

Answer 5

Somme = 100
Additions = (40,30,20,10)

Nombre de 40 s = 100/40 = 2 Remainder = 100% 40 = 20

Nombre de 30 années = 20/30 = 0 = 20% Remainder 30 = 20

Nombre de = 20 de 20/20 = 1 = 20% Remainder 20 = 0

dès que reste = 0 vous pouvez arrêter .

Si vous n'avez plus de factures, vous ne pouvez pas vous rattraper et vous devez passer à la deuxième partie. C'est un problème de minimisation qui peut être résolu avec des méthodes d'algèbre linéaire (je suis un peu rouillé)

Answer 6

Vous savez - Vous avez posé cette même question deux fois maintenant.

What is a good non-recursive algorithm for deciding whether a passed in amount can be built additively from a set of numbers?