Problème de sac à dos: bénéfices égaux

Question

Je recherche des références à des algorithmes efficaces qui résolvent le problème du sac à dos où tous les bénéfices sont égaux.

Définition plus formelle du problème de Un article Wikipedia sur KPS:

Si tous les bénéfices sont 1, nous essaierons de maximiser le nombre d'éléments qui ne dépasseraient pas la capacité de sac à dos:

maximiser $ sum_ {j = 0} ^ n x_j $

sujet à $ sum_ {j = 0} ^ n w_jx_j leq w $,

$ x_j in {0, 1 }, forall_j in {1, ..., n } $

J'ai parcouru Problèmes de sac à dos Livre (Kellerer et al ', 2004) qui est référencé par cet article de Wikipedia mais n'a pas trouvé ce problème particulier.

J'ai également vu quelques articles sur ce problème exact sans bonnes réponses:

• Sac à dos avec la même valeur
• Problème de sac à dos avec tous les bénéfices égaux à 1

La réponse au premier article mentionne le problème de budgétisation des capitaux, mais le lien fourni ne discute pas du cas où tous les bénéfices (valeurs) sont égaux, ce qui, je pense, peut être mieux optimisé en raison de son cas spécial.

La réponse au deuxième article mentionne une solution naïve dans laquelle un algorithme gourmand cueille des éléments de poids minimum à chaque étape jusqu'à ce qu'aucun plus d'articles ne s'intègre dans le sac à dos. Cela nécessite de connaître l'ordre des éléments en poids, ce qui entraîne $ O (n log {n}) $ la solution.

Y a-t-il un algorithme avec une meilleure borne supérieure (par exemple, le temps linéaire)?