Variante du problème du sac à dos

Comment aborderiez-vous le problème du sac à dos dans une situation de programmation dynamique si vous deviez maintenant limiter le nombre d'articles dans le sac à dos par une constante $p$ ? C'est le même problème (poids maximum de , chaque article a une valeur et un poids ) mais vous ne pouvez ajouter que article (s) au sac à dos et vous devez évidemment optimiser la valeur du sac à dos.v w $W$$v$$w$$p$

Avons-nous besoin d'une 3ème dimension ou nous pourrions trouver une autre approche sans elle. J'ai essayé d'ajouter simplement le nombre d'articles dans le sac à dos dans la cellule et de prendre la valeur maximale à la fin avec le nombre d'articles <= mais ce n'est pas la meilleure solution.$p$

Très belle question!

Vous avez deux fois raison:

1. La propagation du nombre d'articles dans le sac à dos ne conduit pas à des solutions optimales.
2. Une solution consiste à ajouter une troisième dimension. C'est assez simple mais il est nécessaire de prendre en compte certains faits. Notez cependant que ce n'est pas la seule alternative

Dans ce qui suit, je suppose que vous connaissez la solution basée sur la programmation dynamique. En particulier, je ne discuterai pas de la façon de parcourir le tableau en arrière pour déterminer la solution .

Concentrons-nous d'abord sur le cas typique: le nombre d'articles n'est pas limité . Dans ce cas, vous venez de construire une table où T i , j contient la valeur optimale lorsque la capacité globale du sac à dos est égale à i et que seuls les j premiers éléments sont pris en compte. D'ici:$T$$T_{i,j}$$i$$j$

$T_{i,j} =\max\{T_{i,j-1}, T_{i-w_j,j-1}+v_j\}$

où et v j support pour le poids et la valeur du j point de -ième respectivement. Si C est la capacité globale de votre havresac et il y a au total N éléments de la solution optimale est donnée par T C , N . Cet algorithme est connu pour fonctionner en temps pseudo-polynomial et l'une de ses beautés est qu'il ne considère que les combinaisons qui correspondent à la capacité maximale.$w_j$$v_j$$j$$C$$N$$T_{C, N}$

Cependant, cela ne suffit pas lors de l'ajout de votre contrainte: un nombre maximum d'éléments . La raison en est que la formule de récurrence précédente ne prend pas en compte différentes combinaisons d'éléments:$p$

1. Tout d'abord, si alors T i , j =( T i - w j , j - 1 + v j ) desorte que lej-ème l'article est ajouté au sac à dos malgré le nombre maximum d'articles considérés,$T_{i,j-1}<(T_{i-w_j,j-1}+v_j)$$T_{i,j}=(T_{i-w_j,j-1}+v_j)$$j$$p$--- afin que vous puissiez violer votre contrainte. Eh bien, vous pourriez être tenté ici d'appliquer la formule précédente en gardant une trace du nombre d'éléments insérés à chaque étape et de ne pas en ajouter d'autres si le nombre d'éléments actuellement dans le sac à dos dépasse mais,$p$
2. Deuxièmement, si alorsT i , j =T i , j - 1 pour que cet élément ne soit pas ajouté mais cela pourrait être une grosse erreur dans le cas où la solution optimaleT i , j - $T_{i,j-1}>(T_{i-w_j,j-1}+v_j)$$T_{i,j}=T_{i,j-1}$$T_{i,j-1}$se compose déjà du nombre maximum d'articles à insérer dans le sac à dos. La raison en est que nous ne comparons pas correctement: d'une part, pour conserver la solution optimale constituée de items sélectionnés parmi les précédents ( j - 1 ) ; d'autre part, à insérer le j article -ième et, en outre envisager le meilleur sous - ensemble à ( p - 1 ) éléments parmi le précédent ( j - 1 ) .$p$$(j-1)$$j$$(p-1)$$(j-1)$

Pour qu'une première solution consiste à ajouter une troisième dimension. Pour votre cas, soit la solution optimale lorsque la capacité du sac à dos est i , seuls les j premiers éléments sont pris en compte et il n'est pas autorisé de mettre plus de k articles dans le sac à dos. Maintenant,$T_{i, j, k}$$i$$j$$k$

• Si vous calculez pour un nombre d'éléments strictement inférieur ou égal au nombre d'éléments pouvant être insérés ( j ≤ k ), procédez comme d'habitude mais en utilisant la même valeur de k : T i , j $T_{i, j, k}$$j\leq k$$k$$T_{i,j,k} =\max\{T_{i,j-1,k}, T_{i-w_j,j-1,k}+v_j\}$
• Maintenant, si vous devez calculer pour un nombre d'éléments strictement supérieur au nombre d'éléments pouvant être insérés ( j > k ) alors: T i , j , k$T_{i, j, k}$$j> k$$T_{i,j,k} =\max\{T_{i,j-1,k}, T_{i-w_j,j-1,k-1}+v_j\}$

La première expression doit être claire. Le second fonctionne puisque la -ième couche de la table T garde la trace de la meilleure combinaison des ( k - 1 ) éléments parmi les premiers ( j - 1 ) comme requis ci-dessus.$(k-1)$$T$$(k-1)$$(j-1)$

Une implémentation efficace de cet algorithme n'a pas besoin de calculer pour tout k . Notez que les relations de récurrence précédentes relient la couche k à ( k - 1 ) et donc, il est possible d'alterner entre deux couches successives (par exemple, si vous êtes intéressé par la solution optimale avec k = 4, vous utilisez simplement deux couches consécutives: 0 et 1, 1 et 2, 2 et 3, 3 et 4 et vous avez terminé). En d'autres termes, cet algorithme prend le double de la mémoire requise par l'approche traditionnelle basée sur la programmation dynamique et peut ainsi être exécuté en temps pseudo-polynomial.$T_{i, j, k}$$k$$k$$(k-1)$$k=4$

Sachez cependant que ce n'est pas la seule solution! Et il y en a un autre que vous pourriez trouver plus élégant. Dans les formules précédentes, nous avons récupéré la solution optimale qui ne comprenait pas plus de éléments parmi les premiers ( j - 1 ) comme $(k-1)$$(j-1)$ . Cependant, il doit être clair que cela est précisément égal à max p = 0 , j - 1 { T i , p$T_{i, j-1, k-1}$$\max\limits_{p=0,j-1}\{T_{i, p}\}$juste en utilisant la table d'origine !! c.-à-d., la solution optimale avec pas plus de articles peut également être récupérée en considérant les solutions optimales avec 1 article, 2 articles, 3 articles, ... ( j - 1 ) articles ... Pour que cette formulation fonctionne, vous devez gardez également une trace du nombre d'éléments pris en compte dans chaque solution partielle de sorte que vous aurez besoin de deux entiers par cellule. Cette occupation de la mémoire entraîne précisément les mêmes besoins en mémoire de l'algorithme illustré ci-dessus (en utilisant une troisième dimension sous la forme de couches k ) .$k$$(j-1)$$k$

J'espère que cela t'aides,