(Re)Bonjour,

J ai un algorithme qui explore toutes les solutions pour un cas a dos de poids p et n objets contant chacun une valeur v et un poids w

Le but est de remplir le sac a dos au maximum (sans depasser le poids p) et avec la combinaison d'objets ayant la plus grande valeur.

Mon algo est rapide pour les poids inferieur a 20 et sur une une sequence de 50 objets. Il me donne la combinaison optimale

J aimerais augmenter le poids jusqu a 100, mais le traitement est tres long

Je me demande si il serai possible de calculer sur un poids de 10 la combinaison optimale, pui de recalculer avec un poids de 10 sur la liste d'objets - la combinaison precedemment trouvé, et ainsi de suite jusqu a 100 puis de concatener toutes les solutions trouvées a chaque fois.

Est ce que je trouverai la solution optimale comme cela ? Ou est ce qu il faudra un traitement intermediaire ?


Merci d avance