knapsack problem

knapsack problem (tsz. knapsack problems)

1. (informatika) hátizsák-probléma

A hátizsák probléma (angolul Knapsack Problem) egy klasszikus kombinatorikus optimalizálási probléma, amely gyakran előfordul az informatikában, műveletek kutatásában, gazdaságban és más alkalmazott tudományokban. A probléma lényege, hogy adott egy hátizsák, amelynek adott a teherbírása (kapacitása), és több különböző tárgy, amelyeknek van súlya és értéke. A cél az, hogy a tárgyak egy részét úgy válasszuk ki, hogy a hátizsák kapacitását ne lépjük túl, és az összérték maximális legyen.

Legyen:

• ${\textstyle n}$: a tárgyak száma.
• ${\textstyle w_{i}}$: az ${\textstyle i}$-edik tárgy súlya.
• ${\textstyle v_{i}}$: az ${\textstyle i}$-edik tárgy értéke.
• ${\textstyle C}$: a hátizsák kapacitása (összsúly, amit elbír).
• ${\textstyle x_{i}\in \{0,1\}}$: döntésváltozó, amely 1, ha az ${\textstyle i}$-edik tárgyat kiválasztjuk, 0, ha nem.

Célfüggvény: ${\textstyle \max \sum _{i=1}^{n}v_{i}\cdot x_{i}}$

Korlátozás: ${\textstyle \sum _{i=1}^{n}w_{i}\cdot x_{i}\leq C}$

Ez az ún. 0-1 hátizsák probléma, mivel minden tárgyból csak egy példány választható (nem darabolható).

A hátizsák problémának több változata is ismert:

• 0-1 hátizsák probléma: minden tárgy vagy teljes egészében bekerül, vagy nem.
• Többszörös hátizsák probléma: több hátizsák áll rendelkezésre.
• Több példányos (unbounded) hátizsák probléma: egyes tárgyakból több is választható.
• Frakcionált hátizsák probléma (fractional knapsack): a tárgyak darabolhatók (pl. ömlesztett áru).
• Multidimenzionális hátizsák: többféle korlát (pl. térfogat és súly).

Tegyük fel, hogy van egy 10 kg kapacitású hátizsákod, és az alábbi tárgyak közül választhatsz:

A cél: olyan kombinációt találni, amely nem haladja meg a 10 kg-ot, és az összérték maximális.

Az összes ${\textstyle 2^{n}}$ kombinációt kipróbáljuk. Ez kis ${\textstyle n}$-re működik, de nagy számú tárgy esetén exponenciális idejű és gyakorlatilag használhatatlan.

Hatékony módszer 0-1 hátizsák problémára. Egy kétdimenziós táblát használunk: ${\textstyle dp}$ jelenti a maximális értéket az első ${\textstyle i}$ tárgyból választva, ha a hátizsák kapacitása ${\textstyle j}$.

Rekurzió:

$${\displaystyle dp={\begin{cases}dp,&{\text{ha }}w_{i}>j\\\max(dp,\ dp+v_{i}),&{\text{egyébként}}\end{cases}}}$$

Időkomplexitás: ${\textstyle O(n\cdot C)}$

Frakcionált esetben (amikor a tárgyak darabolhatók), a válogató módszer (greedy) a legjobb.

Lépések:

1. Rendezés csökkenő ${\textstyle v_{i}/w_{i}}$ szerint.
2. Legnagyobb arányút vesszük először, amíg van hely.
3. Ha egy tárgy már nem fér el, csak egy részét vesszük be.

Ez a módszer optimális frakcionált esetben, de nem működik 0-1 esetben!

A döntési fa mentén végigjárjuk a lehetőségeket, de visszalépünk (cut), ha már nem lehet jobb eredményt elérni. Ez okos keresés kimerítő próbálkozás helyett.

Nagy méretű problémákhoz:

• Genetikus algoritmus
• Szimulált lehűlés (simulated annealing)
• Tabu keresés
• Méhraj optimalizálás (swarm intelligence)

Ezek nem garantálnak optimális megoldást, de nagy problémákra jó közelítő megoldást adnak gyorsan.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int knapsack(int C, vector<int>& weights, vector<int>& values, int n) {
    vector<vector<int>> dp(n+1, vector<int>(C+1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= C; ++w) {
            if (weights > w)
                dp = dp;
            else
                dp = max(dp, dp] + values);
        }
    }
    return dp;
}

int main() {
    vector<int> weights = {2, 3, 5, 4};
    vector<int> values = {3000, 3500, 8000, 4500};
    int capacity = 10;
    int n = weights.size();

    cout << "Max érték: " << knapsack(capacity, weights, values, n) << " Ft" << endl;
}

• Erőforrás-allokáció: pl. idő, pénz, memória optimalizálása.
• Tőzsdei döntések: korlátozott tőkéből a legértékesebb befektetések kiválasztása.
• Tartalomválogatás: pl. hírportálokon, korlátozott helyen a legjobb cikkek megjelenítése.
• Adatkompresszió: bizonyos algoritmusok belső mechanizmusa is kapcsolódik a hátizsák elvhez.

A hátizsák probléma egy NP-teljes probléma, azaz nincs ismert polinomiális idejű algoritmus, amely minden esetben garantáltan megoldja. Ugyanakkor kis méretű példákra dinamikus programozás, míg nagyobb esetekben metaheurisztikus módszerek alkalmazhatók. A probléma nemcsak elméletileg izgalmas, hanem rendkívül gyakorlati jelentőséggel is bír.

• knapsack problem - Szótár.net (en-hu)
• knapsack problem - Sztaki (en-hu)
• knapsack problem - Merriam–Webster
• knapsack problem - Cambridge
• knapsack problem - WordNet
• knapsack problem - Яндекс (en-ru)
• knapsack problem - Google (en-hu)
• knapsack problem - Wikidata
• knapsack problem - Wikipédia (angol)