DAA - Fractional Knapsack

Algorytm Chciwości można bardzo dobrze zrozumieć za pomocą dobrze znanego problemu zwanego problemem plecakowym. Chociaż ten sam problem można rozwiązać, stosując inne podejścia algorytmiczne, podejście Chciwość rozwiązuje problem z frakcyjnym plecakiem rozsądnie w odpowiednim czasie. Omówmy szczegółowo problem plecaka.

Problem z plecakiem

Mając zestaw elementów, z których każdy ma wagę i wartość, określ podzbiór elementów do uwzględnienia w kolekcji, tak aby całkowita waga była mniejsza lub równa podanemu limitowi, a całkowita wartość była jak największa.

Problem plecakowy jest problemem optymalizacji kombinatorycznej. Pojawia się jako podproblem w wielu bardziej złożonych modelach matematycznych rzeczywistych problemów. Jednym z ogólnych podejść do trudnych problemów jest zidentyfikowanie najbardziej restrykcyjnego ograniczenia, zignorowanie pozostałych, rozwiązanie problemu plecakowego i jakoś dostosować rozwiązanie tak, aby spełniało ignorowane ograniczenia.

Aplikacje

W wielu przypadkach alokacji zasobów z pewnym ograniczeniem problem można wyprowadzić w podobny sposób jak problem Knapsacka. Poniżej znajduje się zestaw przykładów.

Znalezienie najmniej marnotrawnego sposobu na cięcie surowców
optymalizacja portfela
Cięcie problemów z zapasami

Scenariusz problemu

Złodziej rabuje sklep i może unieść maksymalny ciężar Wdo jego plecaka. W sklepie dostępnych jest n pozycji i wagai^th pozycja jest w_i a jego zysk jest p_i. Jakie przedmioty powinien zabrać złodziej?

W tym kontekście przedmioty należy dobierać w taki sposób, aby złodziej nosił te przedmioty, za które osiągnie maksymalny zysk. Stąd celem złodzieja jest maksymalizacja zysku.

W zależności od rodzaju przedmiotów, problemy plecakowe są klasyfikowane jako

Ułamkowy plecak
Knapsack

Ułamkowy plecak

W takim przypadku przedmioty można rozbić na mniejsze części, dzięki czemu złodziej może wybierać ułamki przedmiotów.

Zgodnie ze stwierdzeniem problemu

Tam są n przedmioty w sklepie
Waga i^th pozycja $ w_ {i}> 0 $
Zysk za i^th pozycja $ p_ {i}> 0 $ i
Pojemność plecaka to W

W tej wersji problemu plecakowego przedmioty można rozbijać na mniejsze kawałki. Więc złodziej może zająć tylko ułamekx_i z i^th pozycja.

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

Plik i^th item dodaje wagę x_ {i} .w_ {i} $ do całkowitej wagi w plecaku i zysk x_ {i} .p_ {i} $ do całkowitego zysku.

Stąd celem tego algorytmu jest

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

podlegać przymusowi,

$$ \ Displaystyle \ suma \ limity_ {n = 1} ^ n (x_ {i}. w _ {} i) \ leqslant W $$

Oczywiste jest, że optymalne rozwiązanie musi dokładnie wypełnić plecak, w przeciwnym razie moglibyśmy dołożyć ułamek jednego z pozostałych przedmiotów i zwiększyć ogólny zysk.

W ten sposób optymalne rozwiązanie można uzyskać dzięki

$$ \ Displaystyle \ suma \ limity_ {n = 1} ^ n (x_ {i}. w _ {} i) = W $$

W tym kontekście najpierw musimy posortować te elementy według wartości $ \ frac {p_ {i}} {w_ {i}} $, tak aby $ \ frac {p_ {i} +1} {w_ {i } +1} $ ≤ $ \ frac {p_ {i}} {w_ {i}} $. Tutaj,x jest tablicą przechowującą ułamek elementów.

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

Analiza

Jeśli podane pozycje są już posortowane w kolejności malejącej $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $, to whileloop zajmie trochę czasu O(n); W związku z tym całkowity czas obejmujący sortowanie jest wO(n logn).

Przykład

Rozważmy, że pojemność plecaka W = 60 a listę dostarczonych pozycji przedstawia poniższa tabela -

Pozycja	ZA	b	do	re
Zysk	280	100	120	120
Waga	40	10	20	24
Stosunek $ (\ frac {p_ {i}} {w_ {i}}) $	7	10	6	5

Ponieważ podane elementy nie są sortowane według $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $. Po posortowaniu elementy są przedstawione w poniższej tabeli.

Pozycja	b	ZA	do	re
Zysk	100	280	120	120
Waga	10	40	20	24
Stosunek $ (\ frac {p_ {i}} {w_ {i}}) $	10	7	6	5

Rozwiązanie

Po posortowaniu wszystkich elementów według $ \ frac {p_ {i}} {w_ {i}} $. Przede wszystkimB jest wybierana jako waga Bjest mniejsza niż pojemność plecaka. Następny przedmiotA jest wybierana, ponieważ dostępna pojemność plecaka jest większa niż waga A. Teraz,Cjest wybierany jako następny element. Nie można jednak wybrać całego przedmiotu, ponieważ pozostała pojemność plecaka jest mniejsza niż wagaC.

Stąd ułamek C (tj. (60 - 50) / 20).

Teraz pojemność plecaka jest równa wybranym przedmiotom. W związku z tym nie można wybrać więcej pozycji.

Całkowita waga wybranych elementów to 10 + 40 + 20 * (10/20) = 60

A całkowity zysk to 100 + 280 + 120 * (10/20) = 380 + 60 = 440

To jest optymalne rozwiązanie. Nie możemy osiągnąć większego zysku, wybierając inną kombinację przedmiotów.