..
Copyright 2014 Louis Paternault
Cette œuvre de Louis Paternault est mise à disposition selon les termes de
la licence Creative Commons Attribution - Partage dans les Mêmes Conditions
4.0 International (CC-BY-SA). Le texte complet de la licence est disponible
à l'adresse : http://creativecommons.org/licenses/by-sa/4.0/deed.fr
.. _aperitif:
*************************************************************
`aperitif` — Recherche de solutions au problème des apéritifs
*************************************************************
Description du problème
=======================
Le problème des apéritifs est un problème classique d'algorithmique, illustré
par exemple par `Randall Munroe `_ (`traduction française
`_).
Énoncé
------
L'énoncé est le suivant.
* *Version mathématique :* Étant donné un nombre entier :math:`N`, et un
ensemble :math:`X` de :math:`n` nombres :math:`x_i` (pour :math:`i` entier
compris entre 0 et :math:`n-1`), quels éléments de :math:`X`, éventuellement
répétés, ont pour somme :math:`N` ?
* *Version apéritif :* La carte des apéritifs propose un certain nombre
d'éléments, à des prix différents. Quel assortiment puis-je acheter, coûtant
*exactement* une certaine somme d'argent :math:`N` ?
C'est une variation du `problème de la somme
`_.
Difficulté
----------
Ce problème est dit `NP
`_ (il est même
`NP-complet `_). Pour simplifier, il
est très difficile à résoudre, dans le sens où si trouver un algorithme de
résolution peut être assez simple, on ne connait pas d'algorithme *efficace*.
Ainsi, le programme que je propose ici fonctionne bien pour de petites valeurs
du problème, mais c'est tout.
Algorithme
==========
Principe
--------
Étant donnés une liste ``prix``, et un ``total`` à atteindre, on fait comme
suit :
* *(lignes 13 à 15)* Si ``prix`` ne contient qu'un élément, et que ``total``
est un multiple de cet élément, nous avons trouvé une solution.
* *(lignes 17 à 19)* Sinon, on prend le premier élément :math:`x_0` de la
liste, et on cherche, récursivement, des solutions ne contenant pas cet
élément, puis le contenant une fois 1, puis 2, etc. puis :math:`n`, (où
:math:`n` est la partie entière de :math:`\frac{total}{x_0}`).
Code source
-----------
.. literalinclude:: ../jouets/aperitif/__main__.py
:linenos:
:pyobject: aperitif