Dyskretny problem plecakowy (0-1 knapsack problem)


Algorytm zachłanny

  1. Dla każdego przedmiotu wyznacz współczynnik opłacalności v_i / w_i
  2. Posortuj przedmioty malejąco wg tego współczynnika
  3. Dodawaj do rozwiązania kolejne przedmioty zgodnie z tą kolejnością jeżeli nie przekroczy to rozmiaru plecaka W

Przykład


  1. \mathbf{ratio} = [ 0.625, 2.5, 2.5, 0.667, 0.5 ]
  2. \mathbf{v} = [ 5, 5, 2, 5, 1 ]
    \mathbf{w} = [ 2, 2, 3, 8, 2 ]
  3. Wybrano przedmioty: (5, 2), (5, 2), (2, 3), (1, 2)
    \sum \mathbf{x}_i \mathbf{v}_i = 5 + 5 + 2 + 1 = 13
    \sum \mathbf{x}_i \mathbf{w}_i = 2 + 2 + 3 + 1 = 8 \leq 12

Algorytm siłowy (brute force)

  1. Dla każdej wartości i od 0 do 2^n
    1. Zamień i na wektor bitów \mathbf{x}
    2. Jeżeli \sum \mathbf{x}_i \mathbf{w}_i \leq W oraz \sum \mathbf{x}_i \mathbf{v}_i jest najwyższą dotąd odkrytą wartością, to zapamiętaj ją

Przykład


  1. \mathbf{x} = [0, 0, 0, 0, 0]
    \sum \mathbf{x}_i \mathbf{v}_i = 0
    \sum \mathbf{x}_i \mathbf{w}_i = 0
  2. \mathbf{x} = [0, 0, 0, 0, 1]
    \sum \mathbf{x}_i \mathbf{v}_i = 1
    \sum \mathbf{x}_i \mathbf{w}_i = 2
  3. \mathbf{x} = [0, 0, 0, 1, 0]
    \sum \mathbf{x}_i \mathbf{v}_i = 2
    \sum \mathbf{x}_i \mathbf{w}_i = 3
  4. \mathbf{x} = [0, 0, 0, 1, 1]
    \sum \mathbf{x}_i \mathbf{v}_i = 3
    \sum \mathbf{x}_i \mathbf{w}_i = 5

\ldots

  1. \mathbf{x} = [1, 1, 1, 1, 1]
    \sum \mathbf{x}_i \mathbf{v}_i = 19
    \sum \mathbf{x}_i \mathbf{w}_i = 17

Algorytm programowania dynamicznego

  1. Stwórz macierz M_{(n+1) \times (W+1)}
  2. Wypełnij macierz następująco: m_{i,j} = \begin{cases} 0 & \text{gdy } i = 0 \\ 0 & \text{gdy } j = 0 \\ m_{i-1,j} & \text{gdy } w_i > j \\ \max(m_{i-1,j}, v_i + m_{i-1, j-w_i}) & \text{gdy } w_i \leq j \end{cases}
  3. Optymalną wartość plecaka odnajdziemy w komórce m_{n,W}

Przykład

0 1 2 3 4 5 6 7 8 9 10 11 12
0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 5 5 5 5 5
2 0 0 5 5 5 5 5 5 5 5 10 10 10
3 0 0 5 5 10 10 10 10 10 10 10 10 15
4 0 0 5 5 10 10 10 12 12 12 12 12 15
5 0 0 5 5 10 10 11 12 12 13 13 13 15

Odczytywanie wyniku

  1. Niech i=n
  2. Niech j=B
  3. Rozpocznij w komórce m_{i,j}
  4. Powtarzaj dopóki i > 0
    1. Jeżeli wartość w komórce “powyżej” czyli m_{i-1,j} jest taka sama jak wartość w obecnej komórce, to i-ty przedmiot nie został wybrany; kontynuuj od komórki m_{i-1,j}
    2. W przeciwnym razie i-ty przedmiot został wybrany; kontynuuj od komórki m_{i-1,j-w_i}


Generator instancji

Przykłady

  1. n = 2
    X = 12
    W = \frac{3}{4} X = 9

    \mathbf{v} = [ 3, 7 ]
    \mathbf{w} = [ 8, 5 ]c = 13 - 12 = 1\mathbf{w} = [ 7, 5 ]

  2. n = 3
    X = 20
    W = \frac{3}{4} X = 15

    \mathbf{v} = [ 2, 5, 9 ]
    \mathbf{w} = [ 9, 3, 6 ]c = 18 - 20 = -2\mathbf{w} = [ 9, 4, 7 ]

Zadanie

Zadanie rozszerzone (ocena 5.0)