Problème de sacs à dos avec la contrainte exacte du numéro d'article requis

Question

Comment résoudra-t-on le problème du knapsack si nous devions maintenant résoudre le nombre d'éléments dans le knapack par une constante $ l $ ?C'est le même problème (poids maximum de $ w $ , chaque élément a une valeur $ v $ etpoids $ w $ ), mais vous devez ajouter exactement $ l $ article(s) au knapsack (et doit évidemment optimiser la valeur totale du sac à dos).

Tous les sens que j'ai pensé à la mise en œuvre jusqu'à présent (la programmation dynamique, la force brute) a entraîné une défaillance ou des temps de calcul de niveau de vie de l'univers.Toute aide ou idées sont appréciées.

Edit: Je cherche des solutions de temps pseudo-polynomial

Answer 1

Vous pouvez transformer ce problème en une instance de Knapsack. Laissez $ n $ être le nombre d'éléments, $ v $ être la valeur maximale d'un élément et supposons que chaque élément pèse au plus $ w $ (sinon il peut être jeté).

Pour vous assurer que vous sélectionnez au moins $ L $ Articles:

• Ajouter N (V + 1) $ à la valeur de chaque élément.
• Maintenant, le problème est équivalent à celui de maximiser le nombre d'éléments sélectionnés, de briser les liens en faveur de l'ensemble d'éléments présentant une plus grande valeur totale originale, sous réserve des contraintes de poids. Il y a une solution qui sélectionne au moins l $ l $ iFF la solution optimale a une valeur d'au moins $ n (v +1) l $ .

Pour vous assurer de sélectionner au plus $ L $ Articles:

• Ajouter $ (W + 1) $ au poids de chaque article.
• Ajouter $ L (W + 1) $ à $ W $ .
.
• maintenant chaque sous-ensemble de plus que $ l $ articles pèse au moins $ (L + 1) (W + 1 )= L (W + 1) + (W + 1)> L (W + 1) + W $ et n'est donc pas réalisable. Chaque sous-ensemble de $ l $ d'éléments qui avaient un poids total de $ w $ , pèse désormais $ l (w + 1) + w $ , et c'est donc réalisable iff $ w \ le w $ . Un sous-ensemble avec moins de $ l $ peut être réalisable même si son poids global est supérieur à $ w $ , toutefois sa valeur totale sera toujours plus petite que $ n (v + 1) l $ .