Problème de Knapsack avec tous les profits égaux à 1

Question

Il existe une variante du problème du sac à dos où tous les profits sont égaux à 1. Il semble qu'il puisse être résolu beaucoup plus rapidement que le problème classique du sac à dos discret (0-1), mais comment ? Est-ce qu'un simple algorithme gourmand fonctionnera (à chaque itération, on place un objet de poids minimum dans le sac à dos) ?

Answer 1

Je pense que oui.

Intuitivement, étant donné que tous les bénéfices sont égaux à un, du point de vue du bénéfice, vous êtes indifférent aux articles que vous sélectionnez, vous en voulez simplement autant que possible. C'est exactement ce que vous donnera l'algorithme cupide.