Discussion:Problème du rendu de monnaie
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par le projet Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | À évaluer |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Démonstration de NP-complétude.[modifier le code]
"On montre que le problème du rendu de monnaie est NP-difficile par Réduction au problème du sac à dos."
Pour montrer qu'un problème est Np-difficile il faut montrer qu'il existe un problème NP-complet qui s'y ramène polynomialement, pas le contraire. Le fait que ce problème se ramène au problème du sac à dos, montre au mieux qu'il est NP ce qui est de toute façon trivial. Je n'ai malheureusement pas accès à la référence donc je ne peux pas donner plus de précisions. Mais je pense que la phrase ci-dessus est erronée. --Pparent (d) 25 décembre 2011 à 22:09 (CET)
Cas des distributeurs automatiques[modifier le code]
Le problème est de distinguer la suite (fi) des valeurs faciales, la suite (ni) des quantités disponibles, et de trouver la suite (ri) des pièces rendues, telle que
- r <=n (faisabilité)
- r.f= S (exactitude).
1) La complexité est alors bornée par le produit des (ni).
2) Si le disponible est suffisant (r.n)>=S), la réussite de l'algorithme-glouton semble supposer que les valeurs faciales disponibles soient totalement ordonnées par la divisibilité. Ex : rendre 6 auros avec f=(10, 5, 2, 1) et n=(0, 1, 6, 0) échoue si on tente 5+1.
3) Par ailleurs, si on se ramène à un problème d'arithmétique additive, la complexité du rendu est sa hauteur, et les séquences "boites à poids" demanderont de rendre en moyenne un nombre de pièces variant comme le logarithme de la somme à rendre. Les rendus seraient limités à 3 pièces avec une suite de valeurs faciales comme les nombres triangulaires, ou les nombres premiers complétés par 1... --Lf69100 (d) 22 mars 2013 à 23:50 (CET)
arbre?[modifier le code]
Il est dit dans l' "Exemple : calcul de M( 1 , 7 , 23 ) ( 28 )" qu'il s'agit d'une representation en arbre. Mais les arbres n'ont pas de sommets ayant deux antecedants distincts comme c'est le cas ici (20 a pour antécédants 21 et 27 par exemple.)