Ciągły problem z plecakiem

W informatyce teoretycznej ciągły problem plecakowy (znany również jako ułamkowy problem plecakowy ) jest problemem algorytmicznym w optymalizacji kombinatorycznej, w którym celem jest wypełnienie pojemnika („plecak”) ułamkowymi ilościami różnych materiałów wybranych w celu maksymalizacji wartość wybranych materiałów. Przypomina to klasyczny problem plecakowy , w którym przedmioty do umieszczenia w pojemniku są niepodzielne; jednak ciągły problem plecakowy można rozwiązać w czasie wielomianowym , podczas gdy klasyczny problem plecakowy jest NP-trudny . Jest to klasyczny przykład tego, jak pozornie niewielka zmiana w sformułowaniu problemu może mieć duży wpływ na jego złożoność obliczeniową .

Definicja problemu

Przykład ciągłego lub klasycznego problemu plecakowego może być określony przez numeryczną pojemność W plecaka wraz ze zbiorem materiałów, z których każdy ma przypisane dwie liczby: wagę w _i materiału, który jest dostępny do wybrany i całkowitą wartość v _i tego materiału. Celem jest wybranie ilości x _i ≤ w _i każdego materiału, z zastrzeżeniem ograniczenia wydajności

$${\ Displaystyle \ suma _ {i} x_ {i} \ równoważnik W}$$

i maksymalizacji całkowitej korzyści

$${\ Displaystyle \ suma _ {i} x_ {i} v_ {i}.}$$

każda z kwot x _i musi być zerowa lub wi _; ciągły problem plecakowy różni się tym, że x _i zmienia się w sposób ciągły od zera do w _i .

Niektóre sformułowania tego problemu przeskalowują zmienne xi tak _, aby mieściły się w przedziale od 0 do 1. W tym przypadku ograniczenie pojemności staje się

$${\ Displaystyle \ suma _ {i} x_ {i} w_ {i} \ równoważnik W}$$

a celem jest maksymalizacja całkowitej korzyści

$${\ Displaystyle \ suma _ {i} x_ {i} v_ {i}.}$$

Technika rozwiązań

Ciągły problem plecakowy można rozwiązać za pomocą zachłannego algorytmu , opublikowanego po raz pierwszy w 1957 roku przez George'a Dantziga , który uwzględnia materiały w uporządkowanej kolejności według ich wartości na jednostkę masy. Dla każdego materiału ilość x _i jest wybierana tak, aby była jak największa:

• Jeżeli suma dotychczas dokonanych wyborów jest równa pojemności W , to algorytm ustawia x _i = 0.
• Jeśli różnica d między sumą dotychczasowych wyborów a W jest mniejsza niż w _i , to algorytm ustawia x _i = d .
• W pozostałym przypadku algorytm wybiera x _i = w _i .

Ze względu na konieczność sortowania materiałów algorytm ten wymaga czasu O ( n log n ) na wejściach z n materiałami. Jednak adaptując algorytm znajdowania median ważonych , można rozwiązać problem w czasie O ( n ).