the Un problème de changement de monnaie minimum est un Problème NP-Terminé, mais pour certains ensembles de pièces de monnaie, l'algorithme gourmand (choisissez d'abord les plus grandes dénominations). Compte tenu d'un ensemble d'entiers dénotant des valeurs de pièces, quel est l'algorithme le plus rapide pour déterminer si l'algorithme gourmand suffit-il ou non? Une manière évidente consiste à créer votre solution de programmation dynamique jusqu'à la plus grande dénomination et à voir pour chacun si elle donne une meilleure solution que la voie gourmande. Mais y a-t-il une "voie mathémique" plus rapide de la détecter?
4 Réponses :
La solution gourmande ne fonctionne que pour certaines dénominations, en ce qui concerne la certaine quantité pour faire le changement de.
Une étape de ramassage Lorsque vous l'ajoutez, ce n'est plus un gourmand, et cela considère, éventuellement, une recherche toutes les solutions possibles , et ce n'est donc ni un problème de programmation dynamique.
Exemple: considérez la monnaie = [2, 5] et la quantité à modifier est de 16.
Une première solution gourmande cherche naturellement les plus grandes dénominations en premier, [5, 5, 5], puis il restait à 1.
Une étape de raccordement donne une autre solution [5, 5, 2, 2, 2].
L'algorithme gourmand fonctionnerait si la sélection suivante produit le montant cible: (il peut y avoir des formats plus complexes qui fonctionneraient, mais c'est simple et linéaire à vérifier)
let qui est, zéro ou plus sélectionné dans le plus grand et un seul autre élément sélectionné. P> Pourquoi ceci est optimal est simple à prouver. Soit c = les éléments S choisis parmi les plus grands, nous savons que c Produire la somme la plus importante possible pour tous les éléments S ou moins, car, si vous deviez remplacer n'importe quel élément en C, vous devriez le faire avec un bas Élément valorisé, car les plus grands éléments de S sont déjà sélectionnés (et la suppression de la suppression diminuerait évidemment le coût). Puisque C génère une valeur inférieure à la cible (en raison de celui-ci requis), nous avons besoin d'au moins un autre élément pour atteindre la cible, la quantité minimale d'éléments requis pour atteindre la cible est S + 1, qui conclut la preuve. p> vous avez besoin de O (n) pour l'évaluer, ce qui peut être fait comme suit: (en Java) p> 1 code> représente choisi. L'ensemble, de la plus grande dénomination, ressemblerait à: p> int[] sortedCoins = ...;
int sum = 0, selectionCount = 0, i = 0;
for (; i < sortedCoins.length; i++)
{
sum += sortedCoins[i];
if (sum >= target) break;
selectionCount++;
}
sum -= sortedCoins[i]; // we added the element to push us over, so remove it again
for (; i < sortedCoins.length; i++)
{
if (sum + sortedCoins[i] == target)
return selectionCount+1;
}
return -1; // not found
J'ai récemment proposé une solution qui semblait montrer si les 2 conditions données sont satisfaites, l'algorithme gourmand céderait la solution optimale.
a) le g.c.d (toutes les dénominations sauf 1) = 2e plus petite dénomination.
b) La somme de 2 dénominations consécutives doit être inférieure à la 3e dénomination consécutive.
pour par exemple. C2 + C3 (où C1 = 1; C2, C3, C4 sont des dénominations de pièces de monnaie dans l'ordre croissant).
Je comprends que ce n'est pas une solution complète. Cependant, je pense que si ces 2 conditions sont remplies, l'algorithme gourmand cédera la solution optimale.
Exemple d'exemple: un système de monnaie avec {1, 2, 30, 40, 100}, gourmand ne trouvera pas de solution de manière optimale pour 60 = 30 + 30. Il fera 40 + 2 + 2 + 2 + 2 + ... et bientôt.
Le papier de Pearson Un algorithme de temps polynomial pour la Problème de changement de changement Lettres de recherche opérationnelle 33: 3 (mai 2005), p. 231-234 donne un algorithme de temps polynomial pour trouver le contre-exemple minimum à l'algorithme gourmand (s'il existe). Aucune recherche exhaustive requise, son théorème principal se rétrécit beaucoup les candidats beaucoup.
Désolé, je ne comprends pas quel Stackexchange de poser quelle question - il y a Stackoverflow, programmeurs et CS - pourquoi ne pouvons-nous pas avoir un seul site QA? Ou au moins quand je posterai une question, il devrait suggérer s'il y a un similaire dans un autre Stackexchange.
Je sais, mais le meilleur moyen est de lire les FAQ. Je ne me plaignais pas non plus, je détachez simplement un lien pertinent pour aider les personnes qui visitent cette question dans l'espoir d'une réponse :)