0-1 knapsack problem

Angol

Főnév

0-1 knapsack problem (tsz. 0-1 knapsack problems)

(informatika) A hátizsák probléma az operációkutatás és a kombinatorikus optimalizálás egyik legismertebb feladata. Lényege, hogy adott egy korlátozott kapacitású hátizsák, és egy sor tárgy, melyek mindegyike rendelkezik egy súllyal és értékkel. A cél az, hogy a hátizsákba pakolva a tárgyakat:

ne lépjük túl a maximális súlykapacitást,
és maximalizáljuk az összértéket.

2. A 0–1 hátizsák változat

A 0–1 knapsack változatnál minden tárgyat vagy teljesen berakunk (1), vagy egyáltalán nem (0). Nincs lehetőség részleges választásra (ellentétben a frakcionált változattal).

3. Matematikai modell

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 W}$ : a hátizsák maximális kapacitása
${\textstyle x_{i}\in \{0,1\}}$ : döntési változó (1, ha az ${\textstyle i}$ -edik tárgy bekerül, 0 különben)

A modell:

${\begin{aligned}{\text{Maximalizálandó:}}&\quad \sum _{i=1}^{n}v_{i}x_{i}\\{\text{Mellett:}}&\quad \sum _{i=1}^{n}w_{i}x_{i}\leq W\\&\quad x_{i}\in \{0,1\}\quad \forall i\end{aligned}}$

4. Példa

Adott 4 tárgy:

Tárgy	Érték (v)	Súly (w)
1	60	10
2	100	20
3	120	30
4	70	15

A hátizsák kapacitása: W = 50

Megoldás: válasszuk ki azokat a tárgyakat, amelyek összsúlya ≤ 50, de az összérték maximális.

5. Megoldási módszerek

🧮 1. Brute-force (erőből)

Minden lehetséges kombinációt kipróbál: ${\textstyle 2^{n}}$
Kis ${\textstyle n}$ -re működik, de nagyobb méretnél exponenciálisan lassú

💡 2. Dinamikus programozás (DP)

Optimalitás elve alapján részproblémákat old meg
Polinomiális idő: ${\textstyle O(nW)}$
Hatékony, ha ${\textstyle W}$ nem túl nagy

🌲 3. Branch and Bound (B&B)

Teljes keresés, de részproblémák kizárása becslés alapján
Ténylegesen is 0–1 optimalizálásra szabott

📉 4. Heurisztikus módszerek

Gyors, de nem garantáltan optimális
Példa: Greedy algoritmus: legjobb érték/súly arány szerint pakol

6. Dinamikus programozás megközelítése

Készítsünk egy táblázatot ${\textstyle dp[i][w]}$ , ahol:

${\textstyle i}$ : az első ${\textstyle i}$ tárgy figyelembevételével
${\textstyle w}$ : a súlykapacitás

Rekurzív képlet:

$dp[i][w]={\begin{cases}dp[i-1][w],&{\text{ha }}w_{i}>w\\\max(dp[i-1][w],\ dp[i-1][w-w_{i}]+v_{i}),&{\text{ha }}w_{i}\leq w\end{cases}}$

7. Python megvalósítás (DP)

def knapsack(weights, values, W):
    n = len(values)
    dp = [[0] * (W+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for w in range(W+1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][W]

# Teszt
w = [10, 20, 30, 15]
v = [60, 100, 120, 70]
W = 50
print("Max érték:", knapsack(w, v, W))  # Várható eredmény: 170

8. Túlméretezett probléma?

Ha ${\textstyle W}$ nagy szám, akkor a ${\textstyle dp}$ táblázat nagyméretű lesz → memória- és időigény nő
Ilyenkor memóriaoptimalizált megoldás (csak 1D tömb) vagy heurisztika javasolt

9. Kapcsolódó problémák

Probléma	Rövid leírás
Frakcionált hátizsák	Részleges tárgyválasztás is megengedett
Többdimenziós hátizsák	Többféle korlát (pl. térfogat + súly)
Többszörös hátizsák	Több hátizsák, külön korlátokkal
Többször választható	Egyes tárgyakból többet is be lehet pakolni
Subset Sum	Különleges eset: ${\textstyle v_{i}=w_{i}}$ , célösszeg adott

10. Összefoglalás

A 0–1 knapsack probléma egy klasszikus és rendkívül fontos kombinatorikus optimalizálási feladat:

Bináris döntések: minden tárgy vagy bent van, vagy nincs
Cél: maximális érték úgy, hogy súlykorlát nem sérül
Hatékonyen megoldható dinamikus programozással, ha a kapacitás ${\textstyle W}$ nem túl nagy
Valós életbeli alkalmazások:
- Pénzügyi tervezés
- Hordozható eszköz optimalizálás
- Készletgazdálkodás
- Adatcsomagolás

További információk

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