DAA - Zaino frazionario

L'algoritmo Greedy potrebbe essere compreso molto bene con un noto problema denominato problema dello zaino. Sebbene lo stesso problema possa essere risolto impiegando altri approcci algoritmici, l'approccio Greedy risolve il problema dello zaino frazionario ragionevolmente in tempo utile. Parliamo in dettaglio del problema dello zaino.

Problema dello zaino

Dato un insieme di elementi, ciascuno con un peso e un valore, determinare un sottoinsieme di elementi da includere in una raccolta in modo che il peso totale sia inferiore o uguale a un determinato limite e il valore totale sia il più grande possibile.

Il problema dello zaino è nel problema dell'ottimizzazione combinatoria. Appare come un sottoproblema in molti modelli matematici più complessi di problemi del mondo reale. Un approccio generale ai problemi difficili consiste nell'identificare il vincolo più restrittivo, ignorare gli altri, risolvere un problema con lo zaino e in qualche modo aggiustare la soluzione per soddisfare i vincoli ignorati.

Applicazioni

In molti casi di allocazione delle risorse insieme a qualche vincolo, il problema può essere derivato in modo simile al problema dello zaino. Di seguito è riportato un insieme di esempi.

Trovare il modo meno dispendioso per tagliare le materie prime
ottimizzazione del portafoglio
Problemi di stock di taglio

Scenario problematico

Un ladro sta rapinando un negozio e può portare un peso massimo di Wnello zaino. Ci sono n articoli disponibili nel negozio e il peso dii^th l'oggetto è w_i e il suo profitto è p_i. Quali oggetti dovrebbe prendere il ladro?

In questo contesto, gli oggetti dovrebbero essere selezionati in modo tale che il ladro porterà quegli oggetti per i quali otterrà il massimo profitto. Quindi, l'obiettivo del ladro è massimizzare il profitto.

In base alla natura degli articoli, i problemi dello zaino sono classificati come

Zaino frazionario
Knapsack

Zaino frazionario

In questo caso, gli oggetti possono essere suddivisi in pezzi più piccoli, quindi il ladro può selezionare frazioni di oggetti.

Secondo la dichiarazione del problema,

Ci sono n articoli nel negozio
Peso di i^th articolo $ w_ {i}> 0 $
Utile per i^th elemento $ p_ {i}> 0 $ e
La capacità dello zaino è W

In questa versione del problema dello zaino, gli oggetti possono essere suddivisi in pezzi più piccoli. Quindi, il ladro può richiedere solo una frazionex_i di i^th articolo.

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

Il i^th l'elemento contribuisce con il peso $ x_ {i} .w_ {i} $ al peso totale nello zaino e il profitto $ x_ {i} .p_ {i} $ al profitto totale.

Quindi, l'obiettivo di questo algoritmo è

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

soggetto a vincolo,

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

È chiaro che una soluzione ottimale deve riempire esattamente lo zaino, altrimenti potremmo aggiungere una frazione di uno degli elementi rimanenti e aumentare il profitto complessivo.

Pertanto, una soluzione ottimale può essere ottenuta con

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

In questo contesto, prima dobbiamo ordinare quegli elementi in base al valore di $ \ frac {p_ {i}} {w_ {i}} $, in modo che $ \ frac {p_ {i} +1} {w_ {i } +1} $ ≤ $ \ frac {p_ {i}} {w_ {i}} $. Qui,x è un array per memorizzare la frazione di elementi.

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

Analisi

Se gli elementi forniti sono già ordinati in ordine decrescente di $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $, allora il whileloop richiede del tempo O(n); Pertanto, il tempo totale compreso l'ordinamento è inO(n logn).

Esempio

Consideriamo quella la capacità dello zaino W = 60 e l'elenco degli elementi forniti sono riportati nella tabella seguente:

Articolo	UN	B	C	D
Profitto	280	100	120	120
Peso	40	10	20	24
Rapporto $ (\ frac {p_ {i}} {w_ {i}}) $	7	10	6	5

Poiché gli elementi forniti non sono ordinati in base a $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $. Dopo l'ordinamento, gli articoli sono come mostrato nella tabella seguente.

Articolo	B	UN	C	D
Profitto	100	280	120	120
Peso	10	40	20	24
Rapporto $ (\ frac {p_ {i}} {w_ {i}}) $	10	7	6	5

Soluzione

Dopo aver ordinato tutti gli elementi in base a $ \ frac {p_ {i}} {w_ {i}} $. Prima di tuttoB è scelto come peso di Bè inferiore alla capacità dello zaino. Avanti, elementoA è scelto, poiché la capacità disponibile dello zaino è maggiore del peso di A. Adesso,Cviene scelto come elemento successivo. Tuttavia, l'intero articolo non può essere scelto poiché la capacità residua dello zaino è inferiore al peso diC.

Quindi, frazione di C (cioè (60 - 50) / 20) è scelto.

Ora, la capacità dello zaino è uguale agli articoli selezionati. Pertanto, non è più possibile selezionare alcun elemento.

Il peso totale degli articoli selezionati è 10 + 40 + 20 * (10/20) = 60

E il profitto totale è 100 + 280 + 120 * (10/20) = 380 + 60 = 440

Questa è la soluzione ottimale. Non possiamo guadagnare di più selezionando una diversa combinazione di articoli.