27-dars: Knapsack

4-darajaPlatina — dinamik programmalash25–32 darslar

HayotdaSayohat

Ryukzagingiz 8 kilogramm ko’taradi, oldingizda esa o’n xil narsa turibdi. Har birining og’irligi va foydasi bor. Eng foydali to’plamni tanlash kerak — va «eng qimmatidan boshlash» degan tabiiy fikr shu yerda ishlamaydi.

Bu darsdan keyin siz

• ikki o’lchovli holatni ta’riflaysiz va uni bir o’lchovga siqasiz
• ichki siklning yo’nalishi nega muhimligini tushuntirasiz
• tanlovlar soni bilan holatlar soni farqini ayta olasiz

Avval qo’lda

Avval qo‘lda

~7 daqiqa·juftlikda·Qog'oz, 4 ta kichik narsa

To’rtta narsa oling va har biriga og’irlik hamda qiymat yozib qo’ying, masalan (3, 4), (4, 5), (2, 3), (5, 6). Ryukzak quvvati — 7.

Barcha to’plamlarni qog’ozda sanang: har narsa uchun «olaman» yoki «olmayman». Nechta variant chiqdi? Ularning nechtasi 7 ga sig’adi?

Nimani sezishingiz kerak

16 ta variant — 2⁴. To’rtta narsada bu oson, o’ntada 1024 ta, yuztada esa kompyuter ham sanay olmaydi. Demak boshqa yo’l kerak.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Sekin yechim

To’liq izlash har narsa uchun ikki variantni ko’radi: olish yoki olmaslik. Jami 2ⁿ to’plam.

sekin.pyNusxalash

1narsalar = [(3, 4), (4, 5), (2, 3), (5, 6)]2W = 73n = len(narsalar)4eng = 05for tanlov in range(1 << n):6  ogirlik = 07  qiymat = 08  for i in range(n):9      if tanlov & (1 << i):10          ogirlik += narsalar[i][0]11          qiymat += narsalar[i][1]12  if ogirlik <= W and qiymat > eng:13      eng = qiymat14print(eng)

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1narsalar = [(3, 4), (4, 5), (2, 3), (5, 6)]2W = 73n = len(narsalar)4eng = 05for tanlov in range(1 << n):6  ogirlik = 07  qiymat = 08  for i in range(n):9      if tanlov & (1 << i):10          ogirlik += narsalar[i][0]11          qiymat += narsalar[i][1]12  if ogirlik <= W and qiymat > eng:13      eng = qiymat14print(eng)

Sizning bashoratingizTekshirish

Javobni ko'rish

9

Eng yaxshisi — birinchi va ikkinchi narsa: og'irlik 3 + 4 = 7, qiymat 4 + 5 = 9. Bitmask bilan barcha to'plamlarni aylanish 33-darsda batafsil ochiladi.

Nega sekin

Tanlovlar soni 2ⁿ. n = 100 bo’lganda bu son koinotdagi atomlardan ko’p — hech qanday kompyuter yordam bermaydi.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 20	n = 40	n = 100
Barcha to‘plamlar2^n	10⁶sig‘adi	10¹²sig‘maydi	10³⁰sig‘maydi
Holatlar (n × W, W = 10⁵)n	20sig‘adi	40sig‘adi	100sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Tez yechim

DP tanlovlarni emas, holatlarni sanaydi. Holat: «birinchi i ta narsani ko’rdim va ryukzakda j joy ishlatildi». Bunday holatlar soni n × W — narsalar soni 100 bo’lganda ham atigi bir necha million.

Amalda ikki o’lchovli jadval kerak emas: yangi qator faqat oldingisiga bog’liq, shuning uchun bitta qator yetadi.

tez.pyNusxalash

1narsalar = [(3, 4), (4, 5), (2, 3), (5, 6)]2W = 73dp = [0] * (W + 1)4for w, q in narsalar:5  for j in range(W, w - 1, -1):6      if dp[j - w] + q > dp[j]:7          dp[j] = dp[j - w] + q8print(dp)9print(max(dp))

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1narsalar = [(3, 4), (4, 5), (2, 3), (5, 6)]2W = 73dp = [0] * (W + 1)4for w, q in narsalar:5  for j in range(W, w - 1, -1):6      if dp[j - w] + q > dp[j]:7          dp[j] = dp[j - w] + q8print(dp)9print(max(dp))

Sizning bashoratingizTekshirish

Javobni ko'rish

[0, 0, 3, 4, 5, 7, 8, 9]
9

Jadvalning har katagi «shuncha joy bilan erishish mumkin bo'lgan eng yaxshi qiymat»ni saqlaydi. Javob — oxirgi katak, ya'ni to'liq quvvat ishlatilgandagi natija.

Teskari sikl — eng mashhur xato

Beshinchi qator diqqat bilan qaralishi kerak: range(W, w - 1, -1) — ya’ni oxiridan boshiga. Buni oddiy tartibda yozib ko’ramiz.

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1narsalar = [(3, 4)]2W = 73dp = [0] * (W + 1)4for w, q in narsalar:5  for j in range(w, W + 1):6      if dp[j - w] + q > dp[j]:7          dp[j] = dp[j - w] + q8print(dp)

Sizning bashoratingizTekshirish

Javobni ko'rish

[0, 0, 0, 4, 4, 4, 8, 8]

Bitta narsa bor, lekin 6 va 7 quvvatda qiymat 8 chiqdi — ya'ni narsa IKKI MARTA olindi. Sabab: dp[3] shu qadamda yangilangan edi va dp[6] o'sha yangi qiymatdan foydalandi.

▲Bu yerda xato qilishadi

Ichki sikl oldinga yurilsa, shu qadamda qo’yilgan narsa o’sha zahoti qayta ishlatiladi. Kod xato bermaydi va boshqa bir masalani — cheksiz nusxali ryukzakni — yechib qo’yadi. Ikkalasi ham to’g’ri masala, faqat sizga kerakligi boshqasi.

knapsackknapsack problem

Chegaralangan sig’imga eng foydali to’plamni joylash masalasi. Har narsa ko’pi bilan bir marta olinsa — 0/1 knapsack, cheksiz marta olinsa — unbounded knapsack.

Sinab ko’r

Vizualda narsalar birma-bir qo’shiladi. Har qator butun quvvat jadvalini ko’rsatadi: chapdan o’ngga — ryukzakdagi joy.

Knapsack — ikki o'lchovli holat

Ustun — qolgan joy, qator — ko'rilgan narsalar soni. Katakda eng yaxshi qiymat.

Jadval narsalar bo'yicha qator-qator to'ldiriladi; har katakda «olish yoki olmaslik» solishtiriladi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Ustunlar — ryukzakdagi joy (0 dan 7 gacha). Har qator bitta narsa qo'shilgandan keyingi eng yaxshi qiymatni ko'rsatadi.
2. 1-narsa: og'irligi 3, qiymati 4. Har joy uchun ikki variant solishtirildi — narsani olmaslik yoki olib, 3 joy bo'shatish.
3. 2-narsa: og'irligi 4, qiymati 5. Har joy uchun ikki variant solishtirildi — narsani olmaslik yoki olib, 4 joy bo'shatish.
4. 3-narsa: og'irligi 2, qiymati 3. Har joy uchun ikki variant solishtirildi — narsani olmaslik yoki olib, 2 joy bo'shatish.
5. 4-narsa: og'irligi 5, qiymati 6. Har joy uchun ikki variant solishtirildi — narsani olmaslik yoki olib, 5 joy bo'shatish.
6. Javob — oxirgi qatorning eng o'ngi: 9. Jami 18 ta taqqoslash: narsalar soni x quvvat, tanlovlar soni emas.

narsasiz

00000000

1-narsa

2-narsa

3-narsa

4-narsa

Ustunlar — ryukzakdagi joy (0 dan 7 gacha). Har qator bitta narsa qo'shilgandan keyingi eng yaxshi qiymatni ko'rsatadi.

Taqqoslash0

OrqagaO‘ynatishOldinga1/6Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

27 / 40

MasalaHar narsa ko'pi bilan bir marta olinadi. Eng katta qiymatni toping.

Taklif qilingan yechim

1. 1dp[j] — j joy ishlatilganda erishish mumkin bo‘lgan eng katta qiymat.
2. 2Narsalarni birma-bir qo‘shamiz.
3. 3Har narsa uchun j ni w dan W gacha oshirib boramiz.
4. 4Javob — dp dagi eng katta qiymat.

Bu javobning 3-qismi noto'g'ri. Sikl TESKARI yurishi kerak: W dan w gacha. Oldinga yurilsa, shu qadamda yangilangan dp[j - w] o'sha zahoti qayta ishlatiladi va narsa bir necha marta olinadi. Kod xato bermaydi — u boshqa masalani, cheksiz nusxali ryukzakni yechadi.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1Knapsackda holat nima?

Javobni ko'rish

«Birinchi i ta narsani ko’rdim va j joy ishlatildi». Amalda i o’lchovi tashlanadi, chunki yangi qator faqat oldingisiga bog’liq.

2Nega ichki sikl teskari yuradi?

Javobni ko'rish

Har narsa ko’pi bilan bir marta olinishi kerak. Oldinga yurilsa, shu qadamda yangilangan katak o’sha zahoti qayta ishlatiladi.

3Cheksiz nusxali ryukzak uchun nima o'zgaradi?

Javobni ko'rish

Ichki sikl oldinga yuradi. Ya’ni «xato» deb atalgan variant aslida boshqa masalaning to’g’ri yechimi.

4Tanlovlar soni va holatlar soni farqi nima?

Javobni ko'rish

Tanlovlar 2ⁿ — har narsa uchun ikki variant. Holatlar n × W — «nechta narsa ko’rildi va qancha joy ishlatildi». DP ikkinchisini sanaydi.

5W = 10⁹ bo'lsa bu yechim ishlaydimi?

Javobni ko'rish

Ishlamaydi: jadval W uzunlikda va u xotiraga sig’maydi. Bunday chegara boshqa yechim kerakligini bildiradi — masalan qiymat bo’yicha DP yoki meet-in-the-middle.

Masalalar

Masalalar

3 ta

• Book ShopCSES 1158o'rta

  Darsdagi masalaning o‘zi: kitob narxi — og‘irlik, sahifalar — qiymat.

• Money SumsCSES 1745o'rta

  Qiymat emas, ERISHISH MUMKINLIGI saqlanadi. dp mantiqiy qiymatlardan iborat bo‘ladi.

• Two Sets IICSES 1093qiyin

  Yig‘indini teng ikkiga bo‘lish. Nechta usul borligi so‘ralgan, demak dp da sonlar saqlanadi.

Lokal mashq: mashqlar/27-ryukzak/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

To’rtta narsa uchun barcha 16 ta to’plamni jadval qilib yozing: og’irlik, qiymat, sig’adimi. Eng yaxshisini toping va uni darsdagi javob bilan solishtiring.

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

27-ryukzak masalasini yeching. Keyin ichki siklni ataylab oldinga o’zgartiring va sekin.py bilan javoblari qaysi testda farq qilishini toping.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Yechimni o’zgartirib, qaysi narsalar olinganini ham chiqaring. Ishora: jadvalni to’ldirgandan keyin oxiridan orqaga yurib, har qadamda «bu narsa olinganmi?» degan savolga javob bering.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim