Résoudre une variation de 0/1 Knapsack (source multiple pour les éléments, chaque élément peut être sélectionné à partir de l'une des sources)

Question

Donc pour une question de pratique, nous sommes censés concevoir un algorithme de programmation dynamique qui est une variation de 0/1 problème ... au fond de chaque sac article provient de 4 sources différentes, et cet élément peut être pris à partir de seulement l'une des sources ..

A savoir,

S1={(d_k, b_k) | 1 ≤ k ≤ n}, 
S2={(d_k, b_k) | n + 1 ≤ k ≤ 2n}, 
S3={(d_k, b_k) | 2n + 1 ≤ k ≤ 3n}, 
S4 = {(d_k, b_k) | 3n + 1 ≤ k ≤ 4n} 

pour n = 10, si vous sélectionnez i = 16 à mettre, cela signifie que vous ne sélectionnez pas 6, 26 or 36 ...

Pouvez-vous m'aider à résoudre ce problème et à concevoir l'équation de récurrence?

Answer 1

Nous avons des éléments 4n.

Notation:

• V[k] - valeur de k de l'élément (1 < = k < = 4n)
• W[k] - poids de l'élément k (1 < = k < = 4n)
• B - La borne
• f(k,B) - La valeur de la solution optimale lorsque la borne est B et que vous avez 4k éléments.

Pour l'élément kième nous avons cinq choix possibles:

1. Non insertion de l'élément kième à la besace. Sous cette contrainte, la valeur de la solution optimale est f(k-1,B). Pourquoi? parce que nous avons k-1 plus d'éléments et la borne est toujours B.
2. En prenant le kième élément de S1. Sous cette contrainte, la valeur de la solution optimale est V[k] + f(k-1, B - W[k]). Pourquoi? Nous avons gagné V [k] pour le kième élément et W [k]. Donc, pour le reste des éléments, nous allons gagner f (k-1, B - W [k]). Prendre le kième élément de S2. Utilisez la même logique que précédemment pour voir que la valeur de la solution optimale sous cette contrainte est V[k+n] + f(k-1, B - W[k+n]). Prendre le nième élément de S3.
3. optimum: V[k+2n] + f(k-1, B - W[k+2n]). Prendre le nième élément de S4.
4. optimum: V[k+3n] + f(k-1, B - W[k+3n]).

Votre objectif est de maximiser f. D'où l'équation récurrence est:

f(k, B) = 
    max { 
     f(k-1,B),      //you don't take item n 
     V[k] + f(k-1, B - W[k]), //you take item k from S1 
     V[k+n] + f(k-1, B - W[k+n]), //you take item k from S2 
     V[k+2n] + f(k-1, B - W[k+2n]), //you take item k from S3 
     V[k+3n] + f(k-1, B - W[k+3n]) //you take item k from S2 
    } 

Quelle gauche est de trouver les conditions initiales.

Answer 2

Problème de sac à dos 0/1 standard: Pour chaque article, vous ne le prenez pas ou vous ne le prenez pas.

Votre problème: Pour chaque élément, soit vous ne le prenez pas, ou vous le prenez de la source 1, ou ... ou vous le prenez de la source 4.

Maintenant, regardez l'algorithme de programmation dynamique habituel et la relation de récurrence pour le problème du sac à dos 0/1. Regardez d'où vient chaque bit du RHS dans la relation de récurrence; cela correspond à la première déclaration ci-dessus. Adaptez pour utiliser la deuxième déclaration ci-dessus à la place.

(Si je suis un peu cryptique, c'est parce que c'est des devoirs et que vous êtes censé être l'apprentissage :-).)