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"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
modifierLe 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?
modifierIl 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.)