Hátizsák-probléma

1. Sablon:Label

Hátizsák-probléma (Knapsack Problem)

Definíció

A hátizsák-probléma egy kombinatorikai optimalizálási probléma, ahol adott egy hátizsák, amelynek maximális kapacitása (W), és több tárgy, amelyeknek adott a súlya és értéke. A cél az, hogy a hátizsákba úgy válogassuk össze a tárgyakat, hogy az összérték maximális legyen, miközben a súly nem haladja meg a (W)-t.

---

Típusai

1. 0-1 hátizsák-probléma:
   

Minden tárgyat vagy teljes egészében berakunk, vagy nem.

1. Részleges hátizsák-probléma:
   

Tárgyakat darabolhatunk, azaz részben is berakhatók (ezt frakcionált hátizsák-problémának hívjuk).

---

Példa: 0-1 Hátizsák-probléma

Input:

• Tárgyak: (n) darab, minden tárgyhoz adott a súly ((w_i)) és az érték ((v_i)).
• Hátizsák maximális kapacitása: (W).

Kimenet:

• Az összes érték maximális összege.

---

Dinamikus programozás megoldás

Matematikai megközelítés

Az állapotfüggvény: $$K(i,w)=\text{maximális érték az első }i\text{ tárgyból, ha a hátizsák kapacitása }w.$$

Rekurzív reláció: $$K(i,w)=\{\begin{array}{cc}K(i-1,w)& \text{ha }{w}_i>w\\ \text{max}(K(i-1,w),v_i+K(i-1,w-w_i))& \text{ha }{w}_i\le w\end{array}$$

---

Python implementáció

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

    # Töltjük a dinamikus programozási táblát
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                # Max érték: tárgyat berakjuk vagy nem rakjuk be
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
            else:
                # Tárgy nem fér be
                dp[i][w] = dp[i - 1][w]

    # Az optimális érték
    max_value = dp[n][capacity]

    # Kiválasztott tárgyak visszanyerése
    selected_items = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            selected_items.append(i - 1)
            w -= weights[i - 1]

    return max_value, selected_items


# Példa bemenet
values = [60, 100, 120]  # Tárgyak értékei
weights = [10, 20, 30]   # Tárgyak súlyai
capacity = 50            # Hátizsák kapacitása

# Futás
max_value, selected_items = knapsack_01(values, weights, capacity)

print("Maximális érték:", max_value)
print("Kiválasztott tárgyak indexei:", selected_items)

Kimenet:

Maximális érték: 220
Kiválasztott tárgyak indexei: [2, 1]

---

Frakcionált hátizsák-probléma

Ebben a változatban a tárgyakat részlegesen is berakhatjuk. Ez a probléma egy greedy algoritmussal oldható meg, mivel mindig a legmagasabb érték/súly arányú tárgyat választjuk.

Python implementáció (Greedy megoldás)

def fractional_knapsack(values, weights, capacity):
    items = [(values[i] / weights[i], values[i], weights[i]) for i in range(len(values))]
    items.sort(reverse=True, key=lambda x: x[0])  # Érték/súly arány szerint csökkenően rendezve

    total_value = 0
    for ratio, value, weight in items:
        if capacity >= weight:
            # Az egész tárgyat berakjuk
            capacity -= weight
            total_value += value
        else:
            # Csak egy részét rakjuk be
            total_value += ratio * capacity
            break

    return total_value


# Példa bemenet
values = [60, 100, 120]  # Tárgyak értékei
weights = [10, 20, 30]   # Tárgyak súlyai
capacity = 50            # Hátizsák kapacitása

# Futás
max_value = fractional_knapsack(values, weights, capacity)

print("Maximális érték (frakcionált):", max_value)

Kimenet:

Maximális érték (frakcionált): 240.0

---

Összefoglalás

• A 0-1 hátizsák-probléma dinamikus programozással hatékonyan megoldható.
• A frakcionált hátizsák-probléma greedy algoritmussal gyorsan kezelhető, mivel nem igényel rekurziót vagy táblázatot.
• Ezek a problémák jól modellezik az erőforrások optimalizálását számos területen, például logisztikában és pénzügyi tervezésben.

• Sablon:En: Sablon:T