continuous knapsack problem

Angol

Főnév

continuous knapsack problem (tsz. continuous knapsack problems)

1. (informatika) = fractional knapsack problem

---

A continuous knapsack problem (magyarul: folytonos hátizsák probléma) egy optimalizálási probléma, amelyben a tárgyakat tetszőleges mennyiségben lehet bepakolni a hátizsákba, amíg annak kapacitása ki nem merül. Ez szemben áll a 0-1 hátizsák problémával, ahol minden tárgyból vagy az egészet visszük, vagy semmit.

---

📦 Probléma megfogalmazása

Adott:

• ${\textstyle n}$ db tárgy
• Minden tárgynak van egy:
  • értéke ${\textstyle v_{i}}$
  • súlya ${\textstyle w_{i}}$
• A hátizsák maximális súlya: ${\textstyle W}$

Cél: válaszd meg a ${\textstyle x_{i}\in [0,1]}$ frakciókat úgy, hogy:

$${\text{maximalizáld: }}\sum _{i=1}^{n}x_{i}\cdot v_{i}$$

$${\text{úgy, hogy: }}\sum _{i=1}^{n}x_{i}\cdot w_{i}\leq W$$

---

✅ Folytonos megoldás tulajdonságai

• A probléma mindig megoldható és polinomidőben megoldható.
• Nincs szükség dinamikus programozásra: egy egyszerű greedy algoritmus adja az optimális megoldást.

---

⚙️ Greedy algoritmus lépései

1. Számítsd ki minden tárgyra az érték/súly arányt: ${\textstyle {\frac {v_{i}}{w_{i}}}}$
2. Rendezd a tárgyakat csökkenő sorrendbe ezen arány szerint.
3. Menj végig a tárgyakon ebben a sorrendben:
   • Ha még elfér a teljes tárgy, tedd bele (${\textstyle x_{i}=1}$)
   • Ha csak egy része fér bele, akkor részarányosan tedd bele (${\textstyle x_{i}={\frac {W_{\text{hátra}}}{w_{i}}}}$)
   • Ha betelt a hátizsák, fejezd be

---

🧮 Példa

Tárgy	Érték ${\textstyle v_{i}}$	Súly ${\textstyle w_{i}}$	Arány ${\textstyle v_{i}/w_{i}}$
A	60	10	6.0
B	100	20	5.0
C	120	30	4.0

Hátizsák kapacitása: ${\textstyle W=50}$

Lépések:

• Vesszük A-t (teljesen): 10 egység → érték: 60
• Vesszük B-t (teljesen): +20 → érték: 100
• C-ből már csak 20 egység fér: ${\textstyle {\frac {20}{30}}=2/3}$ → érték: ${\textstyle 2/3\cdot 120=80}$

Összérték: 60 + 100 + 80 = 240

---

🧠 TL;DR

A continuous knapsack problem egy optimalizálási probléma, ahol a tárgyakat tetszőleges (folytonos) részarányban lehet bepakolni. A megoldás greedy algoritmussal történik: a legnagyobb érték/súly arányú tárgyakat pakoljuk először, akár tört részben is.

További információk

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