Bizda har biri vaznga va qiymatga ega bo’lgan turli buyumlar bor. Ryukzakga (yoki biror idishga) solish uchun ularni shunday tanlash kerakki, buyumlar ryukzakning maksimum og’irlik limitidan kichkina yoki teng bo’lsin va solingan buyumlarning umumiy qiymati iloji boricha eng kattasi bo’lsin. Ushbu masala ryukzak masalasi, inglizchada knapsack problem deb ataladi. Masalaning turli ko’rinishlari mavjud:
0-1 ryukzak (0-1 knapsack). Buyumlarning har biri bittadan deb olinadi. Bunda qiymatni maksimallashtirish uchun qaysi buyumlarni solish-solmaslik ko’rib chiqiladi.
Chegaralangan ryukzak (bounded knapsack). Buyumlarning har bir turi bitta yoki undan ko’p, ularning har biridan cheklangan n miqdorda olish mumkin.
Chegaralangan ryukzak (bounded knapsack). Buyumlarning har bir turi bitta yoki undan ko’p, ularning har biridan cheklanmagan n miqdorda olish mumkin.
Ko’ptanlovli ryukzak (multiple-choice knapsack). Buyumlar guruhlarga ajratib chiqilgan, har bir guruhdan bittadan buyum olish mumkin.
Masala ryukzakga umuman aloqador bo’lmasligi ham mumkin. Masalan:
Imtihonda testlarning har biriga turlicha ball beriladi. Talaba hamma testni yechishga vaqti yetmaydi, u X tagacha test yecha oladi. U maksimum ball yig’ishi uchun qaysi testlarni yechishi kerak? Bu masala ham ryukzak masalasiga kirib ketadi.
Masalani ishlash tartibi
Biz birinchi masalaga qaytamiz va uni 0-1 ryukzak masalasi deb olib, uni dynamic programming yo’li bilan yechishga urinib ko’ramiz.
Ma’lumotlar: Ryukzak maksimum w = 10 kg gacha ko’tara oladi. Bizda n = 4 ta buyum bor. Ularning qiymati va og’irligi mos holda [10, 40, 30, 50] va [5, 4, 6, 3].
Dastlab biz n + 1 qatorli va w + 1 ustunli ikki o’lchamli array yaratib olamiz. Qator raqami i 1 dan i gacha bo’lgan buyumlarning ro’yhatini beradi. Ustun raqami j ryukzakning sig’imini ifodalaydi. Jadvalni esa qiymatlarni hisoblash orqali to’ldiramiz.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | |||||||||||
| (40) 4 | |||||||||||
| (30) 6 | |||||||||||
| (50) 3 |
Birinchi qatordagi buyumni tekshiramiz. Uning og’irligi = 5, qiymati = 10. Jadvalda 0-4 gacha ryukzak sig’imiga mos kelmaydi (ryukzak sig’imi 0, 1, 2, 3, yoki 4 bo’lganda 5 og’irlikdagi buyum sig’magan bo’lardi), shu sababli birinchi buyum uchun 0 dan 4 gacha 0 qiymat beriladi. Ryukzak sig’imi 5-10 bo’lganda, 5 og’irlikdagi buyum sig’adi. Jadvalga buyumning qiymatini yozamiz.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| (40) 4 | |||||||||||
| (30) 6 | |||||||||||
| (50) 3 |
Ikkinchi buyumni tekshiramiz. Uning og’irligi = 4, qiymati = 40. Jadvalda 0-3 gacha ryukzak sig’imiga mos kelmaydi (ryukzak sig’imi 0, 1, 2, yoki 3 bo’lganda 4 og’irlikdagi buyum sig’magan bo’lardi), shu sababli buyum uchun 0 dan 3 gacha ustunlarga bitta oldingi qatorlardagi qiymatlar – 0 beriladi. 4-ustunda ryukzak sig’imi buyum og’irligiga mos keladi. Ryukzakda buyum bormi? Buni bitta tepadagi yacheykaga tekshiramiz, 0 turipti, demak ryukzak bo’sh. Buyumning qiymatini kiritamiz.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| (40) 4 | 0 | 0 | 0 | 0 | 40 | ||||||
| (30) 6 | |||||||||||
| (50) 3 |
Ikkinchi buyum uchun 5-ustunga keldik. Ryukzak sig’imi 5, buyum sig’imidan ortiq. Agar biz ikkinchi buyumni solsak, 1 og’irlik qoladi. Birinchi buyumning og’irligi 1 dan katta, shuning uchun birinchi buyum qatorida 1 og’irlikka sig’adigan qiymat 0 turipti. Ikkinchi buyumning qiymati 40. Ikkinchi buyumni solamizmi yoki birinchi buyumni qoldiramizmi? Bu yerda qiymatlarning maksimumi olinadi:
Max(40+0, 10) = 40
Demak ikkinchi buyumni solar ekanmiz.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| (40) 4 | 0 | 0 | 0 | 0 | 40 | 40 | |||||
| (30) 6 | |||||||||||
| (50) 3 |
2.6. (ikkinchi buyum, 6-sig’im) Buyum og’irligi 4, ryukzak sig’imi 6. Buyumni solsak, 2 sig’im qoladi. Bitta tepadagi qatorda 2 sig’im uchun qiymat 0 ga teng. Qiymatlarning maksimumi olinadi: Max(40+0, 10) = 40.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| (40) 4 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | ||||
| (30) 6 | |||||||||||
| (50) 3 |
2.7. Buyum og’irligi 4, ryukzak sig’imi 7. Buyumni solsak, 3 sig’im qoladi. Bitta tepadagi qatorda 3 sig’im uchun qiymat 0 ga teng. Qiymatlarning maksimumi olinadi: Max(40+0, 10) = 40.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| (40) 4 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | |||
| (30) 6 | |||||||||||
| (50) 3 |
2.8. Buyum og’irligi 4, ryukzak sig’imi 8. Buyumni solsak, 4 sig’im qoladi. Bitta tepadagi qatorda 4 sig’im uchun qiymat 0 ga teng. Qiymatlarning maksimumi olinadi: Max(40+0, 10) = 40.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| (40) 4 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | ||
| (30) 6 | |||||||||||
| (50) 3 |
2.9. Buyum og’irligi 4, ryukzak sig’imi 9. Buyumni solsak, 5 sig’im qoladi. Bitta tepadagi qatorda 5 sig’im uchun qiymat 10 ga teng. Qiymatlarning maksimumi olinadi: Max(40+10, 10) = 50.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| (40) 4 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | |
| (30) 6 | |||||||||||
| (50) 3 |
2.10. Buyum og’irligi 4, ryukzak sig’imi 10. Buyumni solsak, 6 sig’im qoladi. Bitta tepadagi qatorda 6 sig’im uchun qiymat 10 ga teng. Qiymatlarning maksimumi olinadi: Max(40+10, 10) = 50.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| (40) 4 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | 50 |
| (30) 6 | |||||||||||
| (50) 3 |
Shu tariqa uchinchi buyum uchun hisoblashni davom ettiramiz. Uchinchi buyumning og’irligi 6 bo’lgani uchun ryukzakning 0-5 sig’imiga uchinchi buyum sig’maydi, va bitta oldingi qatordagi qiymatlar qoladi.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| (40) 4 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | 50 |
| (30) 6 | 0 | 0 | 0 | 0 | 40 | 40 | |||||
| (50) 3 |
3.6. Buyum qiymati 30. 6 sig’im – 6 og’irlik = 0 sig’im. Bitta tepadagi qatorda 0 sig’imning qiymati 0 ga teng. Bitta tepadagi yacheyka bilan solishtirib, qiymatlarning kattasi olinadi: Max(30+0, 40) = 40.
3.7. Buyum qiymati 30. 7 sig’im – 6 og’irlik = 1 sig’im. Bitta tepadagi qatorda 1 sig’imning qiymati 0 ga teng. Bitta tepadagi yacheyka bilan solishtirib, qiymatlarning kattasi olinadi: Max(30+0, 40) = 40.
3.8. Buyum qiymati 30. 8 sig’im – 6 og’irlik = 2 sig’im. Bitta tepadagi qatorda 2 sig’imning qiymati 0 ga teng. Bitta tepadagi yacheyka bilan solishtirib, qiymatlarning kattasi olinadi: Max(30+0, 40) = 40.
3.9. Buyum qiymati 30. 9 sig’im – 6 og’irlik = 3 sig’im. Bitta tepadagi qatorda 3 sig’imning qiymati 0 ga teng. Bitta tepadagi yacheyka bilan solishtirib, qiymatlarning kattasi olinadi: Max(30+0, 50) = 50.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| (40) 4 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | 50 |
| (30) 6 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | |
| (50) 3 |
3.10. Buyum qiymati 30. 10 sig’im – 6 og’irlik = 4 sig’im. Bitta tepadagi qatorda 4 sig’imning qiymati 40 ga teng. Bitta tepadagi yacheyka bilan solishtirib, qiymatlarning kattasi olinadi: Max(30+40, 50) = 70.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| (40) 4 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | 50 |
| (30) 6 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | 70 |
| (50) 3 |
Shu tariqa to’rtinchi buyum uchun hisoblashni davom ettiramiz. Uchinchi buyumning og’irligi 3 bo’lgani uchun ryukzakning 0-2 sig’imiga uchinchi buyum sig’maydi, va bitta oldingi qatordagi qiymatlar olinadi.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| (40) 4 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | 50 |
| (30) 6 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | 70 |
| (50) 3 | 0 | 0 | 0 |
4.3. Buyum qiymati 50. 3 sig’im – 3 og’irlik = 0 sig’im. Bitta tepadagi qatorda 0 sig’imning qiymati 0 ga teng. Bitta tepadagi yacheyka bilan solishtirib, qiymatlarning kattasi olinadi: Max(50+0, 0) = 50.
4.4. Buyum qiymati 50. 4 sig’im – 3 og’irlik = 1 sig’im. Bitta tepadagi qatorda 1 sig’imning qiymati 0 ga teng. Bitta tepadagi yacheyka bilan solishtirib, qiymatlarning kattasi olinadi: Max(50+0, 40) = 50.
4.5. Buyum qiymati 50. 5 sig’im – 3 og’irlik = 2 sig’im. Bitta tepadagi qatorda 2 sig’imning qiymati 0 ga teng. Bitta tepadagi yacheyka bilan solishtirib, qiymatlarning kattasi olinadi: Max(50+0, 40) = 50.
4.6. Buyum qiymati 50. 6 sig’im – 3 og’irlik = 3 sig’im. Bitta tepadagi qatorda 3 sig’imning qiymati 0 ga teng. Bitta tepadagi yacheyka bilan solishtirib, qiymatlarning kattasi olinadi: Max(50+0, 40) = 50.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| (40) 4 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | 50 |
| (30) 6 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | 70 |
| (50) 3 | 0 | 0 | 0 | 50 | 50 | 50 | 50 |
4.7. Buyum qiymati 50. 7 sig’im – 3 og’irlik = 4 sig’im. Bitta tepadagi qatorda 4 sig’imning qiymati 40 ga teng. Bitta tepadagi yacheyka bilan solishtirib, qiymatlarning kattasi olinadi: Max(50+40, 40) = 90.
4.8. Buyum qiymati 50. 8 sig’im – 3 og’irlik = 5 sig’im. Bitta tepadagi qatorda 5 sig’imning qiymati 40 ga teng. Bitta tepadagi yacheyka bilan solishtirib, qiymatlarning kattasi olinadi: Max(50+40, 40) = 90.
4.9. Buyum qiymati 50. 9 sig’im – 3 og’irlik = 6 sig’im. Bitta tepadagi qatorda 6 sig’imning qiymati 40 ga teng. Bitta tepadagi yacheyka bilan solishtirib, qiymatlarning kattasi olinadi: Max(50+40, 50) = 90.
4.10. Buyum qiymati 50. 10 sig’im – 3 og’irlik = 7 sig’im. Bitta tepadagi qatorda 7 sig’imning qiymati 40 ga teng. Bitta tepadagi yacheyka bilan solishtirib, qiymatlarning kattasi olinadi: Max(50+40, 50) = 90.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| (40) 4 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | 50 |
| (30) 6 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | 70 |
| (50) 3 | 0 | 0 | 0 | 50 | 50 | 50 | 50 | 90 | 90 | 90 | 90 |
Jadvalni to’ldirdik. Masalada so’ralgan maksimum qiymat jadvalning eng ohirgi yacheykasida turipti: 90. Demak ryukzakga maksimum 90 qiymatli buyumlar solish mumkin ekan.
Aynan qaysi buyumlar olindi?
Buni topish uchun ohirgi yacheykadan orqaga qaytamiz. Ohirgi yacheykaning qiymati – 90. U bitta oldingi qatordan kelmayapti, demak ohirgi qatordagi buyum ryukzakga solingan buyumlar ichida bor.
90 qanday hosil bo’ldi? Ohirgi buyumning og’irligi 3. 90 10-sig’imda turipti. Biz bitta oldingi qatordagi 10 – 3 = 7-sig’imga o’tamiz. 3-qator 7-sig’imning qiymati 40. 40 yuqoridan kelyapti, demak 3-buyum ryukzakga solinmagan.
Biz ikkinchi qator 7-sig’imdamiz. Uning qiymati 40, yuqoridan kelmayapti. Demak ikkinchi buyum ryukzakning ichida. 40 qanday hosil bo’ldi? Ikkinchi buyumning og’irligi 4. Biz bitta oldingi qatordagi 7 – 4 sig’imga o’tamiz. Uning qiymati 0. Demak birinchi buyum ryukzakga solinmagan.
Savolga javob: ikkinchi va to’rtinchi buyumlar ryukzakga solingan.
| (qiymat) og’irlik | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| (10) 5 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| (40) 4 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | 50 |
| (30) 6 | 0 | 0 | 0 | 0 | 40 | 40 | 40 | 40 | 40 | 50 | 70 |
| (50) 3 | 0 | 0 | 0 | 50 | 50 | 50 | 50 | 90 | 90 | 90 | 90 |
Kod
* * *
Men bitta urinishda, maqolalarni o’qish orqali algoritmni tushuna olmagandim. Quyidagi videoni ko’rib chiqqach tushunib oldim.