Résoudre le problème du sac à dos en Java (en)

Le problème du sac à dos est un problème d’optimisation combinatoire célèbre. Son nom vient du fait qu’il modélise une situation comparable à celle du remplissage d’un sac à dos, ne pouvant supporter plus d’un certain poids, avec tout ou partie d’un ensemble donné d’objets. Ces objets ayant chacun un poids et une valeur.

Le but étant de trouver les objets à mettre dans le sac à dos pour maximiser la valeur totale sans dépasser la capacité maximum du sac à dos.

Ce tutoriel montre comment résoudre ce problème en Java à l’aide d’une approche basée sur la programmation dynamique.