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 wagaith pozycja jest wi a jego zysk jest pi. 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 ith pozycja $ w_ {i}> 0 $

  • Zysk za ith 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łamekxi z ith pozycja.

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

Plik ith 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.