Algorithme pour Knapsack avec répétition

Question

J'essaie de concevoir un pseudo-code pour les algorithmes Knapsack, où un seul élément peut être sélectionné plusieurs fois. L'algorithme classique est

OPT(i, w) = max(OPT(i-1, w) or vi + OPT(i-1, w-wi)) 

Afin de répondre aux exigences, je suis en train de modifier à

k=1; 
max = maximum(OPT(i-1, w)) 
while(OPT(i-1, w - k*wi) > 0) { 
    maximum = max(maximum, k*vi + OPT(i-1, w - k*wi)) 
    k++ 
} 
OPT(i, w) = maximum 

Est-ce semble être une solution appropriée? Ou une meilleure solution existe-t-elle? S'il vous plaît laissez-moi savoir si des informations supplémentaires sont requises. Reste tout reste le même, vi désigne la valeur de l'élément ith et wi indique le poids de l'élément ith.

Answer 1

Si vous voulez être en mesure de choisir plusieurs éléments, tout ce que vous avez à faire est de changer la récursion lors de la sélection d'un élément:

OPT(i, w) = max(OPT(i-1, w) or vi + OPT(i, w-wi)) 
        ^    ^
      removed the element  not removing the element 

L'idée est, vous PERMETTENT readding sur l'itération suivante. Vous ajoutez un élément autant que vous le souhaitez, et vous arrêtez de l'ajouter lorsque vous "choisissez" d'utiliser la première condition de la formule d'arrêt récursif. La récursivité ne sera toujours pas infinie car vous devez vous arrêter w<0.

complexité du temps ne change pas - O(nW)

Answer 2

basés sur des algorithmes DVP, la solution à répétition est avec sac à dos comme ci-dessous:

K(0)=0 
for w=1 to W: 
    K(w) = max{K(w - w_i) + v_i, w_i < w} 
return K(W) 

Ici, W est la capacité; w_i est le poids de l'item i; v_i est la valeur de l'item i; K (w) est la valeur maximale réalisable avec le sac à dos de capacité w.

Votre solution ressemble à 0-1 Knapsack cependant.