Masalan n=6, buyumlar og’irliklari 4, 7, 2, 5, 3, 2 bo’lsa, va S=7 o’g’rilikni quyidagicha usullarda olishimiz mumkin;
7, 4+3, 2+5, 5+2, 2+3+2 jami 5 ta usul.
Bizda n ta buyum bor. Biz ulardan tanlash amalga oshirganimzida har bir buyum uchun ikkita variant bor, tanlangan to’plamga tegishliligi yoki tegishli emasligi. n ta razriyadli ikkilik sanoq sistemasida 0 dan 2n-1 gacha bo’lgan sonlarni ikkilikdagi kodida mumkin bo’lgan barcha kombinatsiyalar ko’riladi.
Bizda n ta buyum bor. Biz ulardan tanlash amalga oshirganimzida har bir buyum uchun ikkita variant bor, tanlangan to’plamga tegishliligi yoki tegishli emasligi. n ta razriyadli ikkilik sanoq sistemasida 0 dan 2n-1 gacha bo’lgan sonlarni ikkilikdagi kodida mumkin bo’lgan barcha kombinatsiyalar ko’riladi.
Masalan n=3 bo’lsa 0 dan 23-1 gacha sonlarning ikkilik kodlari:
000 100
001 101
010 110
011 111
Har bir kombinatsiyada sonning ikkilik kodidagi mos belgisi 1 ga teng bo’lsa uni tegishli, 0 ga teng bo’lsa tegishli emas deb olamiz.
Har bir kombinatsiyada sonning ikkilik kodidagi mos belgisi 1 ga teng bo’lsa uni tegishli, 0 ga teng bo’lsa tegishli emas deb olamiz.
Bu usulning ishlash vaqti O(2n n). Demak n≤20 uchun qo’llash mumkin.
Bu usulning ishlash vaqti O(2n n). Demak n≤20 uchun qo’llash mumkin.
Ikkilik pereborni qilishning boshqacha usuli bitli amallar ishlatmasdan, har bir sonni ikkilik sanoq tizimiga o’tkazamiz va har bir belgisini tekshirib chiqamiz:
