Quand un algorithme gourmand peut-il résoudre le problème de changement de pièce?

Étant donné un ensemble de pièces de monnaie de dénominations différentes et une valeur v, vous voulez trouver le moins de pièces nécessaires pour représenter la valeur v. $c1, ... , cn$

Par exemple, pour le jeu de pièces 1,5,10,20, cela donne 2 pièces pour la somme 6 et 6 pièces pour la somme 19.

Ma question principale est: quand peut-on utiliser une stratégie gourmande pour résoudre ce problème?

Points bonus: cette déclaration est-elle tout à fait incorrecte? (De: Comment savoir si un algorithme gourmand suffit pour le problème de changement de pièce minimum? )

Cependant, cet article a une preuve que si l'algorithme gourmand fonctionne pour le premier plus grand denom + les deuxièmes valeurs de denom le plus grand, alors il fonctionne pour tous, et il suggère d'utiliser simplement l'algorithme gourmand vs l'algorithme DP optimal pour le vérifier. http://www.cs.cornell.edu/~kozen/papers/change.pdf

Ps. notez que les réponses dans ce fil sont incroyablement minables - c'est pourquoi j'ai posé la question à nouveau.

algorithms combinatorics greedy-algorithms Le chat unfun
la source

Pour le problème du sac à dos binaire , il existe un critère facilement formulé: un algorithme gourmand résout le problème si pour toutes les dénominations

. Pas si facile pour le changement de pièces (sac à dos avec des variables intégrales arbitraires). Avez-vous besoin d'une exposition de Magazine, Nemhauser et Trotter?

c_{i} > Σ_{j = 1}^{i - 1} c_{j}

$c_i > \Sigma_{j=1}^{i-1} c_j$

Dmitri Chubarov

La déclaration dans l'article de Dexter Kozen dit que si l'algorithme gourmand est d'accord avec l'optimal pour tout

, alors il donnera une solution optimale pour

arbitraire . Je ne vois rien de mal à cette déclaration.

v < c_{n - 1} + c_{n}

$v < c_{n-1} + c_n$

v

$v$

Dmitri Chubarov

@Dmitri Chubarov Merci, maintenant je comprends comment fonctionne le bonus q. Est-ce semblable à une forte induction? Quant à votre autre question, j'aimerais une réponse qui donne une solution et de préférence une preuve.

The Unfun Cat

Je voterai positivement la question et si personne n'intervient, résumez le MNT avec quelques exemples au cours du week-end.

Dmitri Chubarov

Voir aussi cette question connexe ; en particulier, le document lié de Shallit peut être intéressant.

Raphael

Réponses:

Un système de pièces est canonique si le nombre de pièces données en monnaie par l'algorithme gourmand est optimal pour tous les montants.

L'article D. Pearson. Un algorithme à temps polynomial pour le problème de changement. Operations Reseach Letters, 33 (3): 231-234, 2005 propose un algorithme pour décider si un système de pièces est canonique, où est le nombre de différents types de pièces. Du résumé: $O(n^3)$ $n$

Nous dérivons ensuite un ensemble de valeurs possibles qui doivent contenir le plus petit contre-exemple. Chacun peut être testé avec des opérations arithmétiques , nous donnant un algorithme . $O(n^2)$ $O(n)$ $O(n^3)$

Le document est assez court.

$c$ $c$

$O(n^2)$ $n$

Il y a aussi une discussion dans cette question se.math .

Mark Dominus
la source

Merci. Je vois que la question est beaucoup plus complexe que je ne le pensais - je suppose que c'est pourquoi vous n'avez pas posté les critères réels? Mon idée que "si toutes les pièces sont des multiples les unes des autres, l'algorithme gourmand donne un résultat optimal" était évidemment trop simple.

The Unfun Cat

Je n'ai pas posté les critères réels parce que je ne m'en souvenais pas et je n'ai pas eu le temps de relire le papier. Vous devriez, bien sûr, vous sentir libre de modifier ma réponse.

Mark Dominus

J'ai lu la réponse et l'article plusieurs fois, mais je n'ai pas pu trouver de critères lisibles par l'hommecanonical coin system . Ce serait génial si vous pouviez ajouter un exemple, à savoir comment tester le système suggéré1,5,10,20

The Godfather