Ryukzak masalasi

Ryukzak masalasi

Kirish

Ryukzak (sumka) masalasi — bu optimallashtirish masalasi bo‘lib, unda cheklangan sig‘imli ryukzakka (ranetsga) qaysi buyumlarni solish kerakligini aniqlash talab etiladi, shunda umumiy qiymat maksimal bo‘ladi. Buyumlar ham butun, ham kasr bo‘lishi mumkin. Ushbu bobda biz faqat butun sonli variantni (0/1 knapsack) ko‘rib chiqamiz, chunki kasrli variant ochko‘z usul bilan yechiladi.

Qo‘yilish:
$N$ ta buyum berilgan, har birining vazni va qiymati bor, hamda sig‘imi $W$ ($W > 0$) bo‘lgan ryukzak berilgan. Shunday buyumlarni tanlash kerakki, ularning umumiy vazni $W$ dan oshmasin, umumiy qiymati esa maksimal bo‘lsin. Buyumlarni qismlarga bo‘lib bo‘lmaydi.

Misol: $W = 5$, va buyumlar , , (birinchi son — qiymat, ikkinchisi — vazn) ryukzakka va ni solib (vazn ) maksimal qiymat ni olish mumkin.