DSA 0/1 ryukzak masalasi

0/1 ryukzak masalasi

0/1 ryukzak masalasining shartiga ko‘ra, sizda vazn chegarasiga ega ryukzak bor va siz har biri o‘z qiymati va vazniga ega xazinalar bilan to‘la xonadasiz.

0/1 ryukzak masalasini yechish uchun ryukzakning vazn chegarasidan oshmagan holda umumiy qiymatni maksimal qilish uchun qaysi xazinalarni joylashni aniqlashingiz kerak.

Barakalla! Siz maksimal qiymatni beradigan buyumlarni topdingiz😀

1

2

3

Ryukzak

$ {{ totalValue }}

{{ totalWeight }}/{{limit}} kg

{{ item.name }}

$ {{ item.value }}

{{ item.weight }} kg

Yuqoridagi 0/1 ryukzak masalasini qo‘lda yecha olasizmi? 0/1 ryukzak masalasini yechadigan turli amalga oshirishlarni ko‘rish uchun o‘qishda davom eting.

0/1 ryukzak masalasini yechish bizneslarga byudjet doirasida qaysi loyihalarni moliyalashtirishni hal qilishda, ortiqcha xarajat qilmasdan foydani maksimal darajaga yetkazishda yordam beradi. U logistikada ham yuk mashinalari va samolyotlarga yuk ortishni optimallashtirish uchun ishlatiladi: bunda vazn chegaralaridan oshmagan holda eng qimmatli yoki eng yuqori ustuvorlikka ega buyumlar kiritilishi ta’minlanadi.

Brute force yondashuvi

Brute force usulidan foydalanish eng yaxshi natijani izlab, shunchaki barcha imkoniyatlarni tekshirishni anglatadi. Bu odatda masalani yechishning eng to‘g‘ridan-to‘g‘ri usuli, lekin u eng ko‘p hisob-kitobni ham talab qiladi.

0/1 ryukzak masalasini brute force yordamida yechish quyidagilarni anglatadi:

1. Ryukzakdagi buyumlarning har bir mumkin bo‘lgan kombinatsiyasi qiymatini hisoblash.
2. Ryukzakning vazn chegarasidan og‘ir bo‘lgan kombinatsiyalarni chiqarib tashlash.
3. Umumiy qiymati eng yuqori bo‘lgan buyumlar kombinatsiyasini tanlash.

0/1 ryukzak masalasiga bu brute force yondashuvini quyidagicha amalga oshirish mumkin:

def knapsack_brute_force(capacity, n):
    print(f"knapsack_brute_force({capacity},{n})")
    if n == 0 or capacity == 0:
        return 0

    elif weights[n-1] > capacity:
        return knapsack_brute_force(capacity, n-1)

    else:
        include_item = values[n-1] + knapsack_brute_force(capacity-weights[n-1], n-1)
        exclude_item = knapsack_brute_force(capacity, n-1)
        return max(include_item, exclude_item)

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
n = len(values)

print("\nMaximum value in Knapsack =", knapsack_brute_force(capacity, n))

Yuqoridagi kodni ishga tushirish knapsack_brute_force funksiyasi ko‘p marta rekursiv chaqirilishini anglatadi. Buni barcha chiqarilgan natijalardan ko‘rishingiz mumkin.

Funksiya har safar chaqirilganda u joriy buyum n-1 ni yo qo‘shadi, yo qo‘shmaydi.

2-qator: Bu print operatori funksiya har safar chaqirilganini ko‘rsatadi.

3-4-qatorlar: Agar tekshiradigan buyumlar tugasa (n==0) yoki sig‘im tugasa (capacity==0), boshqa rekursiv chaqiruvlar qilmaymiz, chunki bu nuqtada ryukzakka boshqa buyum qo‘shib bo‘lmaydi.

6-7-qatorlar: Agar joriy buyum sig‘imdan og‘ir bo‘lsa (weights[n-1] > capacity), joriy buyumni tashlab, keyingi buyumga o‘ting.

10-12-qatorlar: Agar joriy buyumni ryukzakka qo‘shish mumkin bo‘lsa, qaysi biri eng yuqori qiymatni berishini aniqlang: joriy buyumni qo‘shishmi yoki qo‘shmaslikmi.

Kod misolini ishga tushirish quyidagicha ko‘rinishdagi rekursiya daraxtini hosil qiladi, har bir kulrang quti funksiya chaqiruvini ifodalaydi:

Yuqoridagi rekursiya daraxtidan, masalan, tojni, kubokni va globusni olsak, mikroskop (2 kg) uchun joy qolmasligini va bu bizga jami 200+400+500=1100 qiymat berishini ko‘rish mumkin.

Shuningdek, faqat mikroskopni olish bizga jami 300 qiymat berishini ham ko‘rishimiz mumkin (o‘ng pastki kulrang quti).

Yuqoridagi rekursiya daraxtida va misol kodini ishga tushirib ko‘rganingizdek, funksiya ba’zan bir xil argumentlar bilan chaqiriladi, masalan, knapsack_brute_force(2,0) ikki marta chaqiriladi. Bunga memoizatsiya yordamida yo‘l qo‘ymaymiz.

Memoizatsiya yondashuvi (yuqoridan pastga)

Memoizatsiya usuli oldingi funksiya chaqiruvlari natijalarini massivda saqlaydi, shunda oldingi natijalarni shu massivdan olish mumkin bo‘ladi va ularni qayta hisoblash shart bo‘lmaydi.

Memoizatsiya haqida bu yerda batafsil o‘qing.

Memoizatsiya "yuqoridan pastga" (top-down) yondashuvidir, chunki u masalani tobora kichikroq qism masalalarga qarab pastga harakatlanib yecha boshlaydi.

Yuqoridagi brute force misolida bir xil funksiya chaqiruvlari faqat bir necha marta sodir bo‘ladi, shuning uchun memoizatsiyadan foydalanish samarasi unchalik katta emas. Ammo tanlash uchun ancha ko‘p buyumlar bo‘lgan boshqa misollarda memoizatsiya usuli ko‘proq foyda keltirgan bo‘lardi.

Brute force amalga oshirishini memoizatsiya yordamida yaxshilagandan so‘ng kod endi quyidagicha ko‘rinadi:

def knapsack_memoization(capacity, n):
    print(f"knapsack_memoization({n}, {capacity})")
    if memo[n][capacity] is not None:
        print(f"Using memo for ({n}, {capacity})")
        return memo[n][capacity]
    
    if n == 0 or capacity == 0:
        result = 0
    elif weights[n-1] > capacity:
        result = knapsack_memoization(capacity, n-1)
    else:
        include_item = values[n-1] + knapsack_memoization(capacity-weights[n-1], n-1)
        exclude_item = knapsack_memoization(capacity, n-1)
        result = max(include_item, exclude_item)

    memo[n][capacity] = result
    return result

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
n = len(values)

memo = [[None]*(capacity + 1) for _ in range(n + 1)]

print("\nMaximum value in Knapsack =", knapsack_memoization(capacity, n))

Yuqoridagi koddagi ajratib ko‘rsatilgan qatorlar oldingi brute force amalga oshirishini yaxshilash uchun ishlatilgan memoizatsiya usulini ko‘rsatadi.

24-qator: Oldingi natijalar saqlanadigan memo massivini yarating.

3-5-qatorlar: Funksiya boshida, hech qanday hisob-kitob yoki rekursiv chaqiruv qilishdan oldin, natija allaqachon topilgan va memo massivida saqlanganmi-yo‘qligini tekshiring.

16-qator: Natijani keyinroq foydalanish uchun saqlang.

Tabulyatsiya yondashuvi (pastdan yuqoriga)

0/1 ryukzak masalasini yechishning yana bir usuli — tabulyatsiya deb ataladigan narsadan foydalanish. Bu yondashuv iterativ yondashuv deb ham ataladi va dinamik dasturlashda qo‘llaniladigan usuldir.

Tabulyatsiya masalani pastdan yuqoriga qarab yechadi: jadval avval eng oddiy qism masalalar natijalari bilan to‘ldiriladi. Jadvalning keyingi qiymatlari oldingi natijalardan foydalanib to‘ldiriladi.

Jadval yakuniy natijaga yetguncha oldin hisoblangan qiymatlar yordamida katakma-katak qanday to‘ldirilishini ko‘rish uchun quyidagi animatsiyadan foydalaning.

Ryukzakdagi maksimal qiymatni toping.

1. Jadvalni to‘ldirish uchun "Ishga tushirish" tugmasini bosing.
2. Jadval to‘ldirilgandan so‘ng hisob-kitobni ko‘rish uchun katak qiymatini bosing.

Vaznlar (kg)

Ryukzak sig‘imlari (kg)

Qiymatlar ($)

---

Voy!

{{n-1}}

{{weight}}

{{value}}

{{item.value}}

↓ + =

Ryukzakdagi maksimal qiymat: $ {{ maxValue }}

Tezlik:

Ishga tushirish

Tabulyatsiya yondashuvi ortib boruvchi ryukzak sig‘imlari uchun har safar bitta buyumni ko‘rib chiqish orqali ishlaydi. Shu tarzda yechim avval eng oddiy qism masalalarni yechish orqali quriladi.

Har bir qatorda buyumni ryukzakka qo‘shish ortib boruvchi sig‘imlar uchun ko‘rib chiqiladi.

def knapsack_tabulation():
    n = len(values)
    tab = [[0]*(capacity + 1) for y in range(n + 1)]

    for i in range(1, n+1):
        for w in range(1, capacity+1):
            if weights[i-1] <= w:
                include_item = values[i-1] + tab[i-1][w-weights[i-1]]
                exclude_item = tab[i-1][w]
                tab[i][w] = max(include_item, exclude_item)
            else:
                tab[i][w] = tab[i-1][w]
    
    for row in tab:
    	  print(row)
    return tab[n][capacity]

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
print("\nMaximum value in Knapsack =", knapsack_tabulation())

7-10-qatorlar: Agar buyum vazni sig‘imdan kichik bo‘lsa, demak, uni qo‘shish mumkin. Uni qo‘shish oldingi qatorda hisoblangan, ya’ni buyumni qo‘shmaslikni ifodalovchi natijadan yuqoriroq umumiy qiymat beradimi-yo‘qligini tekshiring. Bu ikki qiymatning eng kattasidan (max) foydalaning. Boshqacha aytganda: joriy buyumni olish yoki olmaslikni tanlang.

8-qator: Bu qatorni tushunish, ehtimol, eng qiyindir. Joriy buyumni qo‘shishga mos keladigan qiymatni topish uchun values massividagi joriy buyum qiymatidan foydalanishimiz kerak. Ammo bundan tashqari, qolgan sig‘im bizga qo‘shimcha qiymat bera oladimi-yo‘qligini ko‘rish uchun sig‘imni joriy buyum vazniga kamaytirishimiz kerak. Bu joriy buyumga qo‘shimcha ravishda boshqa buyumlarni ham qo‘shish mumkinmi-yo‘qligini tekshirish va o‘sha buyumlarning qiymatini qo‘shishga o‘xshaydi.

12-qator: Agar joriy buyum sig‘imdan og‘irroq bo‘lsa (juda og‘ir bo‘lsa), shunchaki oldingi qatordagi qiymatni yozing — u joriy buyumni qo‘shmaslikni ifodalaydi.

Qo‘lda bajarib ko‘rish

Quyida jadvaldagi ayrim qiymatlar qanday hisoblanishi haqidagi izohlar ro‘yxati keltirilgan. O‘qish davomida yaxshiroq tushunish uchun yuqoridagi animatsiyada tegishli jadval katagini bosishingiz mumkin.

Mikroskop, sig‘im 1 kg: Hisoblanadigan birinchi qiymat uchun vazn chegarasi 1 kg bo‘lsa, mikroskopni sumkaga solish mumkinmi-yo‘qligi tekshiriladi. Mikroskop 2 kg keladi, u juda og‘ir, shuning uchun 0 qiymati shunchaki yuqoridagi katakdan nusxalanadi — bu ryukzakda hech qanday buyum yo‘qligiga mos keladi. Vazn chegarasi 1 kg bo‘lgan sumka uchun faqat mikroskopni ko‘rib chiqsak, hech qanday buyum ololmaymiz va $ 0 umumiy qiymat bilan quruq qo‘l bilan ketishimiz kerak.

Mikroskop, sig‘im 2 kg: Hisoblanadigan ikkinchi qiymat uchun 2 kg vazn chegarasida mikroskopni sumkaga sig‘dira olamiz, demak, uni olishimiz mumkin va sumkadagi umumiy qiymat $ 300 (mikroskop qiymati) bo‘ladi. Kattaroq ryukzak sig‘imlari uchun ham faqat mikroskopni ko‘rib chiqsak, uni olishimiz mumkin, shuning uchun o‘sha qatordagi boshqa barcha qiymatlar $ 300 ga teng.

Globus, sig‘im 1 kg: 1 kg og‘irlikdagi globusni va 1 kg ryukzak sig‘imini ko‘rib chiqish globusni olishimiz mumkinligini anglatadi, shuning uchun qiymat $ 200 bo‘ladi. Kod bizga $ 200 beradigan globusni olish va yuqoridagi katakdagi 1 kg sig‘im uchun oldin hisoblangan $ 0 qiymati orasidan maksimalini topadi. Bu holatda globusni olishimiz kerakligi aniq, chunki bunday kichik vaznga ega yagona buyum shu, ammo boshqa holatlarda xuddi shu sig‘imda oldin hisoblangan qiymat yuqoriroq bo‘lishi mumkin.

Globus, sig‘im 2 kg: 2 kg sig‘imda kod globus sig‘ishini ko‘radi, bu bizga $ 200 qiymat beradi, ammo u holda mikroskop sig‘maydi. 2 kg sig‘im uchun mikroskopni qo‘shish esa bizga $ 300 qiymat beradi, bu yuqoriroq, shuning uchun ushbu jadval katagida ryukzak qiymatini maksimal qilish uchun mikroskopni (yuqoridagi katakdagi qiymatni) olish tanlanadi.

Globus, sig‘im 3 kg: Globusni 3 kg sig‘im bilan ko‘rib chiqish globusni olishimiz mumkinligini, qolgan 2 kg sig‘im bilan esa mikroskopni ham olishimiz mumkinligini anglatadi. Bu katakda globus va mikroskopni birga olish faqat mikroskopni olishdan (oldingi qatorda hisoblanganidek) yuqoriroq qiymat 200+300=500 beradi, shuning uchun ikkala buyum ham olinadi va katak qiymati 500 bo‘ladi.

Qaysi buyumlar bizga eng yuqori qiymatni beradi?

Jadvalni to‘ldirib, ryukzak ega bo‘lishi mumkin bo‘lgan maksimal qiymatni topgandan so‘ng ham, bu qiymatni olish uchun qaysi buyumlarni olishimiz kerakligi aniq emas.

Tanlangan buyumlarni topish uchun biz yaratgan jadvaldan foydalanamiz va eng yuqori qiymatli o‘ng pastki katakdan, bizning holatda 1200 qiymatli katakdan boshlaymiz.

Mana, tanlangan buyumlar bosqichma-bosqich usul yordamida qanday topilishining chizmasi:

Vaznlar (kg)

Ryukzak sig‘imlari (kg)

Qiymatlar ($)

---

Voy!

{{n-1}}

{{weight}}

{{value}}

{{item.value}}

↓ + =

Tanlangan buyumlar quyidagicha topiladi:

1. O‘ng pastki qiymat 1200, yuqoridagi katak esa 900. Qiymatlar turlicha, demak, toj tanlangan.
2. Keyingi o‘tadigan katak yuqoridagi qatorda joylashgan va biz tojning vazniga teng marta chapga siljiymiz, ya’ni 3 o‘rin chapga, qiymati 700 bo‘lgan katakka o‘tamiz.
3. Hozir turgan katakning qiymati 700, yuqoridagi katakning qiymati esa 500. Qiymatlar turlicha, demak, joriy qatordagi buyum — kubok tanlangan.
4. Kubok 5 kg keladi, shuning uchun keyingi o‘tadigan katak yuqoridagi qatorda va 5 o‘rin chapda joylashgan — bu globus ko‘rib chiqiladigan qatordagi 300 qiymatli katak.
5. Yuqoridagi katak ham xuddi shu 300 qiymatga ega, demak, globus tanlanmagan va keyingi o‘tadigan katak — mikroskop ko‘rib chiqiladigan, qiymati 300 bo‘lgan bevosita yuqoridagi katak.
6. Yuqoridagi katak qiymati 300 bo‘lgan joriy katakdan farq qilgani uchun mikroskop tanlangan.
7. Keyingi o‘tadigan katak yuqoridagi qatorda va ikki o‘rin chapda, chunki mikroskop 2 kg keladi.
8. Chap yuqori burchakdagi katakka yetib keldik. Qiymat 0 bo‘lgani uchun bu ish tugaganini bildiradi.

Bizning 0/1 ryukzak masalamiz quyidagi buyumlar tanlanganda maksimal qiymatga ega bo‘ladi: toj, kubok va mikroskop.

0/1 ryukzak masalasining yechimini tashkil etuvchi buyumlarni topish uchun xuddi shu qadamlar quyidagi kodga qo‘shilgan.

def knapsack_tabulation():
    n = len(values)
    tab = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                include_item = values[i-1] + tab[i-1][w - weights[i-1]]
                exclude_item = tab[i-1][w]
                tab[i][w] = max(include_item, exclude_item)
            else:
                tab[i][w] = tab[i-1][w]

    for row in tab:
        print(row)

    items_included = []
    w = capacity
    for i in range(n, 0, -1):
        if tab[i][w] != tab[i-1][w]:
            items_included.append(i-1)
            w -= weights[i-1]

    print("\nItems included:", items_included)

    return tab[n][capacity]

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
print("\nMaximum value in Knapsack =", knapsack_tabulation())

Vaqt murakkabligi

0/1 ryukzak masalasini yechishning uchta yondashuvi turlicha va turli vaqt murakkabliklari bilan ishlaydi.

Brute force yondashuvi: Bu uchta yondashuvning eng sekini. Imkoniyatlar rekursiv ravishda \(O(2^n)\) vaqt murakkabligi bilan tekshiriladi, bu yerda \(n\) — olishimiz mumkin bo‘lgan potentsial buyumlar soni. Bu ko‘rib chiqilishi kerak bo‘lgan har bir qo‘shimcha buyum uchun hisoblashlar soni ikki baravar ortishini anglatadi.

Memoizatsiya yondashuvi: Oldingi natijalarni eslab qolish orqali hisoblashlarni tejaydi, natijada yaxshiroq vaqt murakkabligi \(O(n \cdot C)\) ga erishiladi, bu yerda \(n\) — buyumlar soni, \(C\) esa ryukzak sig‘imi. Qolgan jihatlarda bu yondashuv brute force yondashuvi kabi rekursiv tarzda ishlaydi.

Tabulyatsiya yondashuvi: Memoizatsiya yondashuvi bilan bir xil vaqt murakkabligi \(O(n \cdot C)\) ga ega, bu yerda \(n\) — buyumlar soni, \(C\) esa ryukzak sig‘imi, ammo xotiradan foydalanish va ishlash tarzi oldindan bashorat qilinadiganroq, bu esa odatda tabulyatsiya yondashuvini eng maqbul qiladi.