Problèmes de modification avec quelques modifications

Question

En cas de problème de modification avec les algorithmes Greedy suivants, la question suivante se pose: comment faire un montant d'argent donné avec le moins de pièces de monnaie? Algorithme: utilisation des pièces les plus précieuses, si possible. Supposons que nous ayons des nombres infinis de chaque ensemble de pièces.

mon professeur, a écrit le (4) n'est pas produire la solution optimale, tout le monde pourrait dire pourquoi? (Ou pourquoi d'autres ne sont pas contre-?)

1- {1,2,5} 

2- {1,4,7} 

3-{1,5,10} 

4-{1,7,10} 

Answer 1

L'application d'une stratégie gourmande avec des pièces de jeu # 4 ne produira pas un résultat optimal dans une situation où vous devez représenter 14:

• stratégie Greedy prendra 10 dès que possible, en terminant avec quatre penny, pour un total de cinq pièces
• Une stratégie optimale serait de prendre deux sept, pour un total de deux pièces de monnaie.

Il est facile de voir que s'il existe une pièce de monnaie C telle que la valeur k*C peut être composée d'au moins k+1 pièces de monnaie si vous prenez des pièces de monnaie de dénomination plus élevée, l'algorithme glouton ne va pas réussir.

Dans votre dernier jeu , k=2, kC=14. Si vous prenez 10 pour faire 14, vous avez besoin de cinq pièces, ce qui est supérieur à k.