Vaqt murakkabligi
O(n × W)
0/1 Ryukzak muammosi: og‘irligi va qiymati berilgan buyumlar hamda ryukzakning maksimal sig‘imi mavjud. Sig‘imdan oshmagan holda olib ketish mumkin bo‘lgan buyumlarning eng katta umumiy qiymatini topish kerak. Har bir buyumni ko‘pi bilan bir marta olish mumkin.
Ishlash tartibi (Bottom-Up DP):
1. Ikki o‘lchovli jadval yaratiladi: dp[i][w] = dastlabki i ta buyum va w sig‘imdan foydalangandagi maksimal qiymat
2. Har bir i buyum va w sig‘im uchun:
- Agar buyum sig‘masa: dp[i][w] = dp[i-1][w]
- Agar buyum sig‘sa: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
3. dp[n][W] optimal qiymatni o‘z ichiga oladi
Vaqt murakkabligi: O(n × W) — psevdopolinomial
Xotira murakkabligi: O(n × W) — O(W) gacha optimallashtirish mumkin
Qo‘llanilishi:
- Resurslarni taqsimlash
- Byudjetni rejalashtirish
- Yuklarni joylashtirish
- Kriptografiya
Ryukzak muammosi kombinator optimallashtirishning asosiy muammolaridan biri bo‘lib, umumiy holda NP-qiyin hisoblanadi.
O'xshash algoritmlar
Ko'p beriladigan savollar
- 0/1 Ryukzak muammosi (0/1 Knapsack Problem) nima?
- 0/1 Ryukzak muammosi: og‘irligi va qiymati berilgan buyumlar hamda ryukzakning maksimal sig‘imi mavjud. Sig‘imdan oshmagan holda olib ketish mumkin bo‘lgan buyumlarning eng katta umumiy qiymatini topish kerak. Har bir buyumni ko‘pi bilan bir marta olish mumkin.
- 0/1 Ryukzak muammosi (0/1 Knapsack Problem) murakkabligi qanday?
- Vaqt (o'rtacha): O(n × W) · Xotira: O(n × W)
- Ushbu 0/1 Ryukzak muammosi (0/1 Knapsack Problem) vizualizatori kimlar uchun?
- 0/1 Ryukzak muammosi (0/1 Knapsack Problem) vizualizatsiyasi "Dinamik dasturlash" kategoriyasida yuqori darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- 0/1 Ryukzak muammosi (0/1 Knapsack Problem) ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Dinamik dasturlash) quyidagilarni ko'rishingiz mumkin: Fibonacci DP, Longest Common Subsequence. Har biri interaktiv vizualizatsiyaga ega.