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 \(N\), et un ensemble \(X\) de \(n\) nombres \(x_i\) (pour \(i\) entier compris entre 0 et \(n-1\)), quels éléments de \(X\), éventuellement répétés, ont pour somme \(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 \(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 \(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 \(n\), (où \(n\) est la partie entière de \(\frac{total}{x_0}\)).

Code source

 1def aperitif(total, prix):
 2    """Iterateur renvoyant les solutions du problème des apéritifs.
 3
 4    :arg total int: Prix total à atteindre.
 5    :arg prix list: Liste des prix disponibles.
 6
 7    :return: Itérateur sur la liste des solutions, ces solutions étant des
 8             listes correspondant à ``prix``.
 9    """
10    if not prix:
11        return
12
13    if len(prix) == 1:
14        if total % prix[0] == 0:
15            yield [int(total // prix[0])]
16
17    for nombre in range(int((total // prix[0]) + 1)):
18        for solution in aperitif(total - prix[0] * nombre, prix[1:]):
19            yield [nombre] + solution