problème avec tous les bénéfices Knapsack égal à 1

Question

Il y a une variation de problème lorsque tous les bénéfices havresac sont égaux à 1. Il semble qu'il peut être résolu beaucoup plus rapide que problème discret classique havresac (0-1), mais comment? Est-ce que l'algorithme glouton fonctionnera (à chaque itération mettre un objet avec un poids minimum au sac à dos)?

Answer 1

Je le crois.

Intuitivement, étant donné que tous les bénéfices sont égaux à un, du côté de profit que vous êtes indifférent à quels articles que vous choisissez, vous voulez tout autant que vous le pouvez. L'algorithme glouton vous donnera exactement cela.