Poprzedni

8. Problem plecakowy

Problem plecakowy (ang. knapsack problem) jest przykładem zagadnienia optymalizacyjnego, które może być rozwiązywanie za pomocą wielu technik algorytmicznych (oczywiście z różną efektywnością). Niemniej jednak jest to doskonałe „modelowe” zadanie, dzięki któremu jesteśmy w stanie w przybliżony sposób zaprezentować sposoby działania kilku grup algorytmów. O trudności tego problemu niech świadczy fakt, że nie istnieje (przynajmniej nie został jeszcze odkryty) algorytm rozwiązujący dyskretny problem plecakowy, którego pesymistyczna złożoność obliczeniowa byłaby lepsza niż wykładnicza O(2n). Nie powinno nas to dziwić, gdyż problem plecakowy jest głównym przykładem algorytmu tzw. NP-trudnego – szczególnie zainteresowanych tematyką klasyfikacji problemów odsyłamy do naukowej literatury.

Główna zasada tego problemu brzmi: mamy pewien zbiór mniej lub bardziej cennych przedmiotów scharakteryzowanych za pomocą dwóch parametrów:

1. Wartość (cena) przedmiotu i-tego c_i
2. Masa przedmiotu i-tego w_i

Oprócz tych obiektów mamy pewien zbiorczy obiekt, zwyczajowo nazywany plecakiem, który z kolei posiada jeden parametr – całkowitą pojemność W (a ściślej rzecz biorąc powinna być to wytrzymałość na obciążenie). Zadanie jakie stoi przed osobą, która dokonuje załadunku przedmiotów do plecaka (zamiast  turysty wyruszającego na długą wyprawę w opisach tego zadania często spotykany jest  np.  złodziej w muzeum sztuki), jest następujące:

  • Należy dokonać takiego wyboru przedmiotów do plecaka, by ich sumaryczna wartość była możliwie maksymalna, zachowując przy tym ograniczenia dotyczące pojemności W plecaka.

Poniżej przedsatwiono kod aplikacji, która przy pomocy programowania dynamicznego rozwiązuje problem plecakowy: 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Funkcja rozwiązująca problem plecakowy 0-1
int knapsack(const vector<int>& val, const vector<int>& wt, int W) {
    int n = val.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    // Budowanie tabeli dp
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (wt[i - 1] <= w) {
                dp[i][w] = max(
                    dp[i - 1][w],                         // nie bierzemy przedmiotu
                    dp[i - 1][w - wt[i - 1]] + val[i - 1] // bierzemy przedmiot
                );
            } else {
                dp[i][w] = dp[i - 1][w]; // nie zmieści się więc nie bierzemy
            }
        }
    }

    return dp[n][W]; // maksymalna wartość możliwa do uzyskania
}

int main() {
    vector<int> val = {60, 100, 120};
    vector<int> wt = {10, 20, 30};
    int W = 50;

    cout << "Maksymalna wartość, którą można zmieścić w plecaku: "
         << knapsack(val, wt, W) << endl;

    return 0;
}
  Poprzedni