Tout à commencé lorsque j’ai regardé la vidéo de David Louapre sur sa chaine Science étonnante Nos algorithmes pourraient-ils être BEAUCOUP plus rapides ? (P=NP ?). J’ai été fasciné par ces problèmes si simple au premier abord et pourtant si complexe à coder.

Après m’être amusé à faire quelques tests avec le problème SAT, basé sur l’exemple de la vidéo, je décide aujourd’hui de m’attaquer au problème du sac à dos.

J’ai trouvé quelques données de test sur le site https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html. J’ai restructuré ces données au format JSON, le format est un tableau structuré de cette façon :

[
  {
    "capacity": 26,
    "best": 51,
    "list": [
      {
        "weight": 12,
        "profit": 24,
        "keep": false
      },
      {
        "weight": 7,
        "profit": 13,
        "keep": true
      },
      {
        "weight": 11,
        "profit": 23,
        "keep": true
      },
      {
        "weight": 8,
        "profit": 15,
        "keep": true
      },
      {
        "weight": 9,
        "profit": 16,
        "keep": false
      }
    ]
  }
]

Celui-ci est le second exemple, voici les détails sur les clés en prenant l’exemple du sac à dos :

• capacity : capacité totale du sac
• best: meilleure solution (selon le fournisseur du jeu de données)
• list : les produits
  • weight : poids du produit
  • profit : prix
  • keep : true si le jeu de données considère qu’il fait partie du meilleur choix

Le but est de trouver quel est le meilleur profit possible en fonction de la capacité du sac.

Il est peu probable que je trouve une solution, en tout cas performante, sur une grande quantité de données. Cependant, j’aime ce genre de défi, d’une part pour travailler ma logique pour réaliser un algorithme et en même temps me rendre compte de la complexité de ce fascinant problème.

Si vous souhaitez essayer, je vous invite à télécharger le fichier restructuré au format JSON (GNU LGPL license.).