DAA - Sac à dos fractionnaire

L'algorithme Greedy pourrait être très bien compris avec un problème bien connu appelé problème Knapsack. Bien que le même problème puisse être résolu en employant d'autres approches algorithmiques, l'approche Greedy résout raisonnablement le problème du sac à dos fractionné dans un délai raisonnable. Discutons en détail du problème de Knapsack.

Problème de sac à dos

Étant donné un ensemble d'éléments, chacun avec un poids et une valeur, déterminez un sous-ensemble d'éléments à inclure dans une collection afin que le poids total soit inférieur ou égal à une limite donnée et que la valeur totale soit aussi grande que possible.

Le problème du sac à dos est un problème d'optimisation combinatoire. Il apparaît comme un sous-problème dans de nombreux modèles mathématiques plus complexes de problèmes du monde réel. Une approche générale des problèmes difficiles consiste à identifier la contrainte la plus restrictive, à ignorer les autres, à résoudre un problème de sac à dos et à ajuster d'une manière ou d'une autre la solution pour satisfaire les contraintes ignorées.

Applications

Dans de nombreux cas d'allocation de ressources avec une certaine contrainte, le problème peut être dérivé d'une manière similaire au problème de Knapsack. Voici un ensemble d'exemples.

Trouver le moyen le moins coûteux de réduire les matières premières
optimisation du portefeuille
Réduire les problèmes de stock

Scénario de problème

Un voleur vole un magasin et peut porter un poids maximal de Wdans son sac à dos. Il y a n articles disponibles dans le magasin et le poids dei^th l'élément est w_i et son profit est p_i. Quels objets le voleur doit-il emporter?

Dans ce contexte, les objets doivent être sélectionnés de manière à ce que le voleur porte les objets pour lesquels il réalisera un profit maximum. Par conséquent, l'objectif du voleur est de maximiser le profit.

En fonction de la nature des articles, les problèmes de sac à dos sont classés comme

Sac à dos fractionnaire
Knapsack

Sac à dos fractionnaire

Dans ce cas, les objets peuvent être divisés en morceaux plus petits, le voleur peut donc sélectionner des fractions d'objets.

Selon l'énoncé du problème,

Il y a n articles dans le magasin
Poids de i^th article $ w_ {i}> 0 $
Profiter pour i^th item $ p_ {i}> 0 $ et
La capacité du sac à dos est W

Dans cette version du problème Knapsack, les articles peuvent être divisés en plus petits morceaux. Donc, le voleur ne peut prendre qu'une fractionx_i de i^th article.

$$ 0 \ leqslant x_ {i} \ leqslant 1 $$

le i^th item contribue le poids $ x_ {i} .w_ {i} $ au poids total dans le sac à dos et le profit $ x_ {i} .p_ {i} $ au profit total.

Par conséquent, l'objectif de cet algorithme est de

$$ maximiser \: \ Displaystyle \ sum \ limits_ {n = 1} ^ n (x_ {i} .p _ {} i) $$

soumis à contrainte,

$$ \ displaystyle \ sum \ limits_ {n = 1} ^ n (x_ {i} .w _ {} i) \ leqslant W $$

Il est clair qu'une solution optimale doit remplir exactement le sac à dos, sinon nous pourrions ajouter une fraction de l'un des articles restants et augmenter le profit global.

Ainsi, une solution optimale peut être obtenue par

$$ \ displaystyle \ sum \ limits_ {n = 1} ^ n (x_ {i} .w _ {} i) = W $$

Dans ce contexte, nous devons d'abord trier ces éléments en fonction de la valeur de $ \ frac {p_ {i}} {w_ {i}} $, de sorte que $ \ frac {p_ {i} +1} {w_ {i } +1} $ ≤ $ \ frac {p_ {i}} {w_ {i}} $. Ici,x est un tableau pour stocker la fraction d'éléments.

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

Une analyse

Si les éléments fournis sont déjà triés dans un ordre décroissant de $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $, alors la boucle whileloop prend un certain temps dans O(n); Par conséquent, le temps total, y compris le tri, estO(n logn).

Exemple

Considérons que la capacité du sac à dos W = 60 et la liste des éléments fournis sont indiqués dans le tableau suivant -

Article	UNE	B	C	ré
Profit	280	100	120	120
Poids	40	dix	20	24
Ratio $ (\ frac {p_ {i}} {w_ {i}}) $	sept	dix	6	5

Comme les éléments fournis ne sont pas triés en fonction de $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $. Après le tri, les éléments sont comme indiqué dans le tableau suivant.

Article	B	UNE	C	ré
Profit	100	280	120	120
Poids	dix	40	20	24
Ratio $ (\ frac {p_ {i}} {w_ {i}}) $	dix	sept	6	5

Solution

Après avoir trié tous les éléments selon $ \ frac {p_ {i}} {w_ {i}} $. Tout d'abordB est choisi comme poids de Best inférieure à la capacité du sac à dos. Prochain pointA est choisi, car la capacité disponible du sac à dos est supérieure au poids du A. Maintenant,Cest choisi comme élément suivant. Cependant, l'article entier ne peut pas être choisi car la capacité restante du sac à dos est inférieure au poids deC.

Par conséquent, une fraction de C (c'est-à-dire (60 - 50) / 20) est choisi.

Désormais, la capacité du sac à dos est égale aux articles sélectionnés. Par conséquent, aucun autre élément ne peut être sélectionné.

Le poids total des articles sélectionnés est 10 + 40 + 20 * (10/20) = 60

Et le profit total est 100 + 280 + 120 * (10/20) = 380 + 60 = 440

C'est la solution optimale. Nous ne pouvons pas gagner plus de profit en sélectionnant une combinaison différente d'articles.