DAA - Sac à dos 0-1

Dans ce didacticiel, nous avons abordé précédemment le problème du sac à dos fractionnaire en utilisant l'approche Greedy. Nous avons montré que l'approche Greedy donne une solution optimale pour Fractional Knapsack. Cependant, ce chapitre couvrira le problème 0-1 Knapsack et son analyse.

Dans 0-1 Knapsack, les articles ne peuvent pas être cassés, ce qui signifie que le voleur doit prendre l'article dans son ensemble ou le laisser. C'est la raison pour laquelle il s'appelle 0-1 Knapsack.

Par conséquent, dans le cas de 0-1 Knapsack, la valeur de x_i peut être soit 0 ou 1, où les autres contraintes restent les mêmes.

0-1 Knapsack ne peut pas être résolu par une approche cupide. L'approche gourmande ne garantit pas une solution optimale. Dans de nombreux cas, l'approche Greedy peut donner une solution optimale.

Les exemples suivants établiront notre déclaration.

Exemple 1

Considérons que la capacité du sac à dos est W = 25 et les articles sont comme indiqué dans le tableau suivant.

Article	UNE	B	C	ré
Profit	24	18	18	dix
Poids	24	dix	dix	sept

Sans considérer le profit par unité de poids (p_i/w_i), si nous appliquons l'approche Greedy pour résoudre ce problème, premier élément Asera sélectionnée car elle contribuera max _i profit mum entre tous les éléments.

Après avoir sélectionné l'élément A, aucun autre élément ne sera sélectionné. Par conséquent, pour cet ensemble donné d'éléments, le profit total est24. Alors que la solution optimale peut être obtenue en sélectionnant des éléments,B et C, où le profit total est 18 + 18 = 36.

Exemple-2

Au lieu de sélectionner les éléments en fonction de l'avantage global, dans cet exemple, les éléments sont sélectionnés sur la base du rapport p _i / w _i . Considérons que la capacité du sac à dos est W = 60 et les articles sont comme indiqué dans le tableau suivant.

Article	UNE	B	C
Prix	100	280	120
Poids	dix	40	20
Rapport	dix	sept	6

Utilisation de l'approche gourmande, premier élément Aest sélectionné. Ensuite, l'élément suivantBest choisi. Par conséquent, le profit total est100 + 280 = 380. Cependant, la solution optimale de cette instance peut être obtenue en sélectionnant des éléments,B et C, où le profit total est 280 + 120 = 400.

Par conséquent, on peut conclure que l'approche cupide peut ne pas donner une solution optimale.

Pour résoudre 0-1 Knapsack, une approche de programmation dynamique est nécessaire.

Énoncé du problème

Un voleur vole un magasin et peut porter un max _i poids de malWdans son sac à dos. Il y an articles et poids de i^th l'élément est w_i et le bénéfice de la sélection de cet article est p_i. Quels objets le voleur doit-il emporter?

Approche de programmation dynamique

Laisser i être l'élément le plus numéroté dans une solution optimale S pour Wdollars. ensuiteS^' = S - {i} est une solution optimale pour W - w_i dollars et la valeur de la solution S est V_i plus la valeur du sous-problème.

Nous pouvons exprimer ce fait dans la formule suivante: définir c[i, w] être la solution pour les objets 1,2, … , iet le poids max _i mumw.

L'algorithme prend les entrées suivantes

• Le poids max _i mumW

• Le nombre d'articles n

• Les deux séquences v = <v₁, v₂, …, v_n> et w = <w₁, w₂, …, w_n>

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if wi ≤ w then 
         if vi + c[i-1, w-wi] then 
            c[i, w] = vi + c[i-1, w-wi] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w]

L'ensemble des éléments à prendre peut être déduit du tableau, à partir de c[n, w] et remonter la provenance des valeurs optimales.

Si c [i, w] = c [i-1, w] , alors itemi ne fait pas partie de la solution, et nous continuons à tracer avec c[i-1, w]. Sinon, itemi fait partie de la solution, et nous continuons à tracer avec c[i-1, w-W].

Une analyse

Cet algorithme prend θ ( n , w ) fois car la table c a ( n + 1). ( W + 1) entrées, où chaque entrée nécessite θ (1) temps pour calculer.