Операции со битови

Во претходното предавање зборувавме за декадниот и бинарниот броен систем. Накратко, споменавме како во декадниот броен систем, секоја цифра вреди 10 пати повеќе од цифрата која се наоѓа десно од неа (единици, десетки, стотки, итн). На пример, кај бројот 589 (5*100 + 8*10 + 9), имаме 9 единици, 8 десетки и 5 стотки. Со други зборови, кај овој број, цифрата која се наоѓа кај десетките има 10 пати поголема вредност од цифрата која се наоѓа кај единиците. Слично, цифрата која се наоѓа кај стотките има 10 пати поголема вредност од цифрата која се наоѓа кај десетките – и 100 пати поголема вредност од онаа која се наоѓа кај единиците.

Кај бинарниот броен систем, секоја цифра вреди 2 пати повеќе од цифрата која се наоѓа десно од неа. Кај овој броен систем, постојат две можни цифри (1 и 0), кои уште ги нарекуваме и битови. На пример, 1101 (запишано бинарно) има вредност 13 (разгледувано во декаден броен систем), бидејќи 1101 = 1*23+1*22+0*21+1*20 = 1*8+1*4+0*2+1*1 = 13. Слично, во претходното предавање зборувавме како може да претвораме броеви од еден броен систем во друг. Иако тоа не е задолжително за сфаќање на идеите и алгоритмите кои ќе ги разгледуваме тука, сепак би препорачал, доколку имате проблеми со сфаќање на основните операции кај бинарниот броен систем, да го разгледате претходното предавање, па потоа да се вратите на овој дел.

Операции со битови

Програмскиот јазик C++ ни овозможува, кога сакаме да вршиме операции врз броеви, да пишуваме наредби користејќи го декадниот броен систем - иако, самиот компјутер, операциите ќе ги извршува користејќи единици и нули. На пример, во програмскиот јазик C++ можеме да напишеме наредба каде вредноста “5+3*9” ќе ја сместиме во променливата “x”, и компјутерот во таа променлива ќе ја смести соодветната вредност. Во овој дел, ќе зборуваме за наредби кои вршат операции врз самите битови (единиците и нулите) од броевите. Понатаму, при крајот на ова предавање, ќе видиме како ова можеме да го искористиме за решавање на многу различни проблеми - користејќи едноставен алгоритам кој ќе можете да го применувате често.

Да започнеме со операторите & (И), | (ИЛИ) и ^ (XOR), и разгледување како тие функционираат врз позитивни броеви (ова е објаснето и во другиот курс, за основите на програмскиот јазик C++, но тука ќе го повториме). Имено, за дадени два броја x и y, ако ги разгледуваме нивните битови на секоја позиција (на пример, гледано од десно на лево), првиот оператор (&) ќе ја изврши операцијата И врз сите битови од двата броја кои се наоѓаат на иста позиција, бит по бит (И означува дека новата вредност ќе биде 1 ако битовите кај двата броја се 1). Од друга страна, операторот | ќе ја изврши операцијата ИЛИ (што означува дека новата вредност ќе биде 1, ако на таа позиција барем еден од битовите е 1). Кај операторот ^ (XOR), вредноста ќе биде 1 ако битовите кои се наоѓаат на таа позиција имаат различна вредност (едниот има 1, а другиот 0).

Како пример, да ги разгледаме следните три изрази: 153&172, 153|172 и 153^172. Запишано бинарно, 153=10011001, додека 172=10101100. Самиот начин на претворање од еден броен систем во друг го разгледавме во претходното предавање, но тоа не е важно за сфаќање на материјалот. Конкретно, овие два броја (153 и 172), ги користиме (само) како пример. Операциите (И, ИЛИ и XOR) најлесно може да ги разбереме доколку ги запишеме двата броја (операнди) еден до друг. Откога ќе го направиме тоа, потребно е да ја извршиме соодветната операција на секоја колона:

10011001 (153)
&&&&&&&&
10101100 (172)
========
10001000 (136)

Значи, 153&172 е еднакво на 136. Забележете дека операцијата И (AND) ја спроведовме врз секој пар од битови (бит од едниот број и бит од другиот број, за секоја колона посебно), и, во резултатот, имаме единица (1) кај колоните каде и двата бита се единици. Во овој случај, и двата броја ги запишавме со по 8 бита, но доколку едниот од броевите е мал (на пример 3), секогаш можеме да додадеме нули од левата страна (кај позначајните битови), бидејќи тие не ја менуваат вредноста на бројот: 3 е 00000011 запишано бинарно.

Да продолжиме понатаму - со разгледување на вредноста на изразот 153|172.

10011001 (153)
||||||||
10101100 (172)
========
10111101 (189)

Значи, 153|172 е еднакво на 189. Повторно, операцијата ИЛИ (OR) ја спроведовме врз секој пар од битови - и, во резултатот, имаме единица (1) кај колоните каде барем еден бит е единица.

Следно, да ја разгледаме операцијата XOR, т.е. вредноста на изразот 153^172.

10011001 (153)
^^^^^^^^
10101100 (172)
========
00110101 (53)

Значи, 153^172 е еднакво на 53, и имаме единици во оние колони каде што точно еден од битовите е 1, а другиот е 0 (со други зборови, двата бита во таа колона се различни).

Следно, да разгледаме уште два оператори кои ќе ни бидат од корист: поместување битови на лево (<<), и поместување на битови на десно (>>). Пред да продолжиме понатаму, имајте во предвид дека, освен сличниот начин на запишување ('>>' и '<<'), не постои никаква поврзаност помеѓу операторите за поместување на битови и операторите за читање на податоци (cin >> x;) или печатење на податоци (cout << x;).

Операторот << врши поместување во лево на битовите кои се наоѓаат во еден број (оној кој ќе го наведеме на левата страна од операторот), онолку пати колку што изнесува вредноста која што ќе ја наведеме од десната страна на операторот. На пример, кај x << n, ги поместуваме битовите кои се наоѓаат во променливата x, за n места налево. На пример, ако x = 11 (00001011 запишано бинарно), и напишеме 11 << 1, ќе ја добиеме вредноста 00010110 (како да сме го избришале битот кој беше најлево, и да сме додале една нула на крајот од бројот). Со други зборови, забележете дека, кога работиме со позитивни броеви (како во овој случај), при поместување во лево, битовите кои се наоѓаат најлево (најзначајните битови) се губат, а од десната страна доаѓа 0.

Да разгледаме уште неколку примери:

(11 << 1) == 22, бидејки 11 e 00001011 (запишано бинарно), а по поместувањето налево, добиваме 22 (00010110)
(11 << 2) == 44, бидејки 11 e 00001011 (запишано бинарно), а по поместувањето налево, добиваме 44 (00101100)
(11 << 3) == 88, бидејки 11 e 00001011 (запишано бинарно), а по поместувањето налево, добиваме 88 (01011000)

(1 << 0) == 1, бидејќи 1 е 00000001 (запишано бинарно), но поместуваме налево за 0 битови, па вредноста останува иста (бидејќи, всушност, и нема поместување)
(1 << 1) == 2, бидејќи 1 е 00000001 (запишано бинарно), а по поместувањето налево, добиваме 2 (00000010)
(1 << 2) == 4, бидејќи 1 е 00000001 (запишано бинарно), а по поместувањето налево, добиваме 4 (00000100)
(1 << 3) == 8, бидејќи 1 е 00000001 (запишано бинарно), а по поместувањето налево, добиваме 8 (00001000)
(1 << 4) == 16, бидејќи 1 е 00000001 (запишано бинарно), а по поместувањето налево, добиваме 16 (00010000)
(1 << 5) == 32, бидејќи 1 е 00000001 (запишано бинарно), а по поместувањето налево, добиваме 32 (00100000)

Сигурно забележавте дека вредноста на изразот (1 << n) е еднаква на 2n (1, 2, 4, 8, 16, 32, итн). На пример, кај изразот (1 << 5) добивме вредност 32, што е 25=32. Дополнително, забележете дека сите степени на 2 се број кој, во бинарниот запис, има само една единица (1=0001, 2=0010, 4=0100, 8=1000, итн). Ова ќе ни послужи во продолжението на ова предавање, кога ќе решаваме конкретни проблеми.

Покрај за поместување во лево, постои и оператор >>, кој овозможува поместување во десно на битовите кои се наоѓаат во еден број (оној кој ќе го наведеме на левата страна од операторот), онолку пати колку што изнесува вредноста која што ќе ја наведеме од десната страна на операторот. На пример, кај x >> n, ги поместуваме битовите кои се наоѓаат во променливата x, за n места надесно. На пример, ако x = 11 (00001011 запишано бинарно), и напишеме 11 >> 1, ќе ја добиеме вредноста 00000101 (како да сме го избришале битот кој беше најдесно, и да сме додале една нула на почетокот од бројот). Со други зборови, забележете дека, кога работиме со позитивни броеви (како во овој случај), при поместување во десно, битовите кои се наоѓаат најдесно (најнезначајните битови) се губат, а од левата страна доаѓа 0.

Да разгледаме и неколку примери кај овој оператор:

(11 >> 1) == 5, бидејки 11 e 00001011 (запишано бинарно), а по поместувањето надесно, добиваме 5 (00000101)
(12 >> 1) == 6, бидејки 12 e 00001100 (запишано бинарно), а по поместувањето надесно, добиваме 6 (00000110)
(12 >> 2) == 3, бидејки 12 e 00001100 (запишано бинарно), а по поместувањето надесно, добиваме 3 (00000011)

(1 >> 0) == 1, бидејќи 1 е 00000001 (запишано бинарно), но поместуваме надесно за 0 битови, па вредноста останува иста (бидејќи, всушност, и нема поместување)
(1 >> 1) == 0, бидејќи 1 е 00000001 (запишано бинарно), а по поместувањето надесно, добиваме 0 (00000000)

(8 >> 1) == 4, бидејќи 8 е 00001000 (запишано бинарно), а по поместувањето надесно, добиваме 4 (00000100)
(8 >> 2) == 2, бидејќи 8 е 00001000 (запишано бинарно), а по поместувањето надесно, добиваме 2 (00000010)
(8 >> 3) == 1, бидејќи 8 е 00001000 (запишано бинарно), а по поместувањето надесно, добиваме 1 (00000001)
(8 >> 4) == 0, бидејќи 8 е 00001000 (запишано бинарно), а по поместувањето надесно, добиваме 0 (00000000)

Овој оператор (за поместување во десно) нема да го користиме во ова предавање, но интересно е да се забележи како, по поместување надесно за 1 добиваме вредност која е двапати помала (како да делиме со 2, притоа отфрлајќи го остатокот од делењето). Слично, по поместување надесно за 2, добиваме вредност која е четири пати помала (како да делиме со 4); по поместување надесно за 3, добиваме вредност која е осумпати помала (како да делиме со 8), итн.

Корисни операции

Да замислиме дека имаме променлива x, во која е сместен некој позитивен број. Како што видовме претходно, одреден број можеме да го разгледуваме во повеќе бројни системи. Во овој дел, бидејќи зборуваме за операции со битови, нека го разгледуваме бројот x во бинарниот броен систем. Ако бројот го разгледуваме во овој систем, знаеме дека секоја цифра може да е 0 или 1. Овој факт дека еден број можеме да го разгледуваме бит по бит, ни овозможува да користиме броеви за чување на множества. Поконкретно, секоја цифра (на пример, гледајќи го бројот од десно на лево), може да ни означува дали некој елемент е во множеството (1) или не е во множеството (0). На овој начин, користејќи само една променлива од целоброен податочен тип, можеме да чуваме множества од вредности.

На пример, нека ги имаме следните потенцијални елементи {0, 1, 2, 3, 4, 5, 6, 7}. Сега, може да ги разгледуваме следните вредности:

00000001 - во множеството има само еден елемент (0), бидејќи имаме само една единица (најдесниот бит)
00000100 - во множеството има само еден елемент (2), бидејќи имаме само една единица (третиот бит од десно, па зборуваме за третата вредност од можните елементи наведени погоре)
00000011 - во множеството има два елементи (0 и 1)
00010101 - во множеството има три елементи (0, 2 и 4)

Сега, да разгледаме 3 основни операции кои можеме да ги направиме врз едно множество (број). Најпрвин, доколку сакаме да додадеме нова вредност во множеството, потребно е само да го поставиме (на 1) соодветниот бит во променливата. Поконкретно, ако променливата е x, можеме да ја искористиме следната наредба за поставување на нејзиниот n-ти бит:

x = x | (1 << n)

Оваа наредба функционира бидејќи операторот | (ИЛИ, кој веќе го видовме погоре) враќа нова вредност, каде што битот на одредена позиција е 1 кога тој бит е 1 или во бројот кој се наоѓа на левата страна (во случајов x), или во бројот кој се наоѓа на десната страна (во случајов, 1 << n). Поконкретно, ова значи дека не ги менуваме битовите кои се веќе 1 во бројот x (тие елементи кои се веќе во множеството), но од изразот (1 << n) ќе добиеме бит 1 и на позиција n. Ова следува од фактот дека веќе видовме како (1 << n) е вредност која има само еден поставен бит (оној на позиција n).

Втората операција која ќе ја видиме е како да избришеме одреден елемент од множеството (ако веќе знаеме дека истиот се наоѓа таму). Ова можеме да го направиме користејќи ја наредбата:

x = x ^ (1 << n)

Внимавајте, оваа наредба функционира само доколку n-тиот бит (во бројот x) има вредност 1 - само во тој случај наредбата ќе го постави n-тиот бит на вредност 0. Доколку истиот е веќе еднаков на 0, оваа операција ќе ја смени вредноста во 1, т.е. ќе има ист ефект како и додавање на вредноста во множеството (нешто што го видовме со претходната наредба). Имено, ова следува од фактот што операторот ^ (XOR) враќа вредност 1 ако битот на одредена позиција во бројот кој се наоѓа на левата страна (во случајов x) е различен од битот кој се наоѓа во бројот на десната страна (во случајов, 1 << n). Бидејќи (1 << n) е вредност која има само еден поставен бит (бит еднаков на 1), само таа вредност ќе биде променета во бројот x, и тоа n-тиот бит ќе биде поставен на 0 (доколку тој е 1), или ќе биде поставен на 1 (доколку тој е 0). Сите останати ќе си ја задржат својата вредност, бидејќи сите други битови во (1 << n) се еднакви на 0 - па ако битот на таа позиција во x е 1, тој ќе остане 1 (бидејќи XOR помеѓу 1 и 0 е 1); а доколку битот на таа позиција во бројот x е 0, тој ќе остане 0 (бидејќи XOR помеѓу 0 и 0 e 0).

Третата операција која што ќе ја разгледаме е онаа која што е всушност и најважна: како да провериме дали еден бит е 0, или тој бит е 1? Знаејќи го решението на овој проблем, ако имаме променлива x во која чуваме множество од вредности, со оваа операција ќе можеме да видиме дали одреден елемент се наоѓа во множеството или не. Изразот кој ќе го користиме за оваа проверка е:

(x & (1 << n)) != 0

Со други зборови, ќе провериме дали изразот (x & (1 << n)) е еднаков на 0, или не. Доколку изразот е еднаков на 0, тоа значи дека n-тиот бит е еднаков на 0 (т.е., дека тој елемент не се наоѓа во множеството). Во спротивно, знаеме дека n-тиот бит е еднаков на 1. Овој израз функционира бидејќи операторот & (И) ќе врати вредност каде што битот на одредена позиција ќе биде 1 ако тој е 1 и во бројот од левата страна на операторот, и во бројот од десната страна. Во спротивно, битот ќе биде 0, ако тој е нула барем кај еден од броевите. Бидејќи (1 << n) има само еден бит еднаков на 1 (оној на n-тата позиција), изразот (x & (1 << n)) ќе врати број кој што има најмногу еден бит еднаков на 1 (оној на n-тата позиција), и тоа само во случај доколку тој е 1 и во бројот x. Ако n-тиот бит е 0 во бројот x, вредноста на изразот (x & (1 << n)) ќе биде 0, бидејќи сите битови ќе бидат еднакви на 0, што ни означува дека тој елемент не се наоѓа во множеството кое е претставено преку бројот x.

Подмножества

Множество кое има N елементи има точно 2N подмножества. На пример, ако имаме множество од три елементи {0, 1, 2}, постојат точно 23=8 подмножества. Тие се:

три подмножества со 1 елемент: {0}, {1}, {2}
три подмножества со 2 елементи: {0, 1}, {0, 2}, {1, 2}
едно подмножество со 3 елементи: {0, 1, 2}
едно празно подмножество со 0 елементи: {}

Ако имаме 4 елементи, постојат 24=16 подмножества од тие елементи. Слично, за 5 елементи постојат 25=32 подмножества, итн. Имајќи ја во предвид претходната дискусија за претставување на множества преку разгледување на битовите кај една променлива од целоброен тип (на пример, int), тука можеме да видиме како сите подмножества можеме да ги генерираме (создадеме) само со користење на бројач (for циклус) кој ќе се движи од 0 до 2N (s=0; s<(1 << N); s++). Забележете како го искористивме фактот дека 2N може да се добие користејќи го операторот за поместување на лево (1 << N), што го откривме погоре при разгледувањето на ефектите од поместување на битови во лево.

Да разгледаме конкретен пример. Имено, кај множеството {0, 1, 2} имаме 3 елементи, па да видиме како со броевите од 0 до 7 (вкупно 2N=8 броеви) можеме да ги претставиме сите подмножества:

0: или бинарно 000 (гледајќи ги само последните 3 битови), го означува празното подмножество {}
1: или бинарно 001, го означува подмножеството {0}, бидејќи само последниот бит е еднаков на 1 (последниот бит го означува елементот 0, претпоследниот елементот 1, итн). Со други зборови, првиот бит од позади означува дали елементот 0 е присутен, вториот од позади дали елементот 1 е присутен, а третиот бит од позади дали елементот 2 е присутен
2: или бинарно 010, го означува подмножеството {1}, бидејќи само претпоследниот бит е еднаков на 1
3: или бинарно 011, го означува подмножеството {0, 1}, бидејќи последниот и претпоследниот бит се еднакви на 1
4: или бинарно 100, го означува подмножеството {2}, бидејќи само третиот бит од позади е еднаков на 1
5: или бинарно 101, го означува подмножеството {0, 2}
6: или бинарно 110, го означува подмножеството {1, 2}
7: или бинарно 111, го означува подмножеството {0, 1, 2}, бидејќи сите битови се еднакви на 1

Како што можете да забележите, разгледувајќи ги броевите од 0 до 7, ги споменавме сите осум подмножества на {0, 1, 2}. Слично, можеме да ги создаваме сите подмножества на множества со 4, 5, 6, 7, 8, или повеќе елементи. Оваа идеја ќе ни овозможи да пишуваме кратки и едноставни решенија за различни проблеми.

Броеви чиј збир е еднаков на X

Користејќи ги поимите и идеите кои ги разгледавме претходно, да се обидеме да решиме неколку проблеми, за да видиме како може да се применат множествата и битовите на разни задачи. Да започнеме со следниот проблем: имаме низа од неколку цели броеви (на пример, [1, 3, 2, 5, 7, 6, 3, 3]), и даден ни е цел број X (на пример, 15). Дали е можно да се одберат неколку броеви од низата, така што нивниот збир (сума) е еднаква на X?

Овој проблем можеме да го решиме преку создавање на сите подмножества на броевите од низата. Во нашиот конкретен пример, имаме низа од 8 елементи, значи вкупно има 28=256 подмножества. Притоа, кога ќе ги разгледуваме овие подмножества како цели броеви (0, 1, 2, 3, 4, 5, ... 255), секој бит од бројот ќе ни означува дали елементот на таа позиција во низата е во подмножеството или не. На пример, кај бројот 5 (00000101), имаме два битови кои се еднакви на 1 (првиот од позади, и третиот од позади), што означува дека во овој случај разгледуваме подмножество каде ги имаме првиот и третиот елемент од низата. Бидејќи ќе ги разгледаме сите броеви од 0 до 2N, всушност ќе ги испробаме и сите потенцијални решенија, со што заклучуваме дека нашата идеја за решавање на овој проблем е соодветна.

Извадок 14.1

bool find_subset(vector<int> numbers, int X)
{
     int N = numbers.size();
     
     for(int s=0; s < (1 << N); s++)   //s go oznachuva podmnozhestvoto
     {
          int sum = 0; //sumata na elementite koi se del od ova podmnozhestvo
          
          //presmetaj ja sumata na elementite od ova podmnozhestvo
          for(int i=0; i<N; i++)
          {
               if ((s & (1 << i)) != 0)  //proveruvame dali i-tiot bit vo 's' e 1
               {
                    //i-tiot bit vo 's' e 1, znachi vo ova 
                    //podmnozhestvo go imame i-tiot element
                    sum += numbers[i];
               }
          }
          
          if (sum == X)
          {
               //najdovme podmnozhestvo so suma X
               return true;
          }
     }
     
     //ne pronajdovme podmnozhestvo so suma X
     return false;
}

Делот каде проверуваме дали еден бит е еднаков на 1 со изразот ((s & (1 << i)) != 0) е објаснет на почетокот на ова предавање. Доколку не ви е јасно зошто функционира истиот, вратете се на почетокот на предавањето, и разгледајте го делот за “Корисни операции”, каде зборувавме за начинот на менување на битови кај броевите, и за проверка дали еден бит е еднаков на 1 или на 0. Инаку, овој проблем може да се реши (се разбира, на друг начин) и со помош на динамичко програмирање. Дискусијата ќе ја продолжиме подолу, по разгледувањето на уште еден проблем и неговото решение.

Проблем на ранец

Овој проблем веќе го разгледавме во едно од претходните предавања. Најпрвин, да се потсетиме дека кај истиот, се обидуваме да направиме најдобар избор на предмети кои може да ги земеме во еден ранец. Поконкретно, имаме неколку предмети, и за секој предмет ни е позната неговата тежина (на пример, во килограми), и неговата вредност (на пример, во денари). Доколку имаме ранец кој има капацитет од C килограми, која е најголемата вредност која што може да се постигне при најдобриот избор на предмети кои ќе ги ставиме во ранецот? Не можеме да ги ставиме сите, ако нивната тежина е поголема од капацитетот на ранецот.

Како пример, ако имаме ранец со капацитет од 10 килограми, и три предмети: ламба (од 2 килограми, и вредност од 100 денари), книга (од 2 килограми, и вредност од 300 денари), и лаптоп (од 8 килограми, и вредност од 30000 денари), најдобриот избор е да ги земеме лаптопот и книгата (вкупна тежина од 10 килограми), за вкупна вредност од 30300 денари. Не можеме да ги земеме сите три предмети, бидејќи нивната заедничка тежина е 12 килограми, а ранецот има капацитет од 10 килограми.

Како можеме да го решиме овој проблем, користејќи го она што го научивме во ова предавање? Да размислиме. Очигледно, и тука, имаме множество од елементи (во случајов, предмети). Доколку ги создадеме сите можни подмножества, ќе ги испробаме сите комбинации од предмети кои може да се земат во еден ранец, па можеме за секое подмножество да провериме дали тежината на предметите е соодветна (помала од капацитетот на ранецот), и за оние подмножества со соодветна тежина, можеме да чуваме кое од нив има најголема вредност на предметите. Решението изгледа вака:

Извадок 14.2

int knapsack(vector<int> weight, vector<int> value, int C)
{
     int N = weight.size();
     int bestValue = 0;        //koe e najdobroto reshenie dosega?
     
     for(int s=0; s < (1 << N); s++)
     {
          int currentWeight = 0;
          int currentValue = 0;
          
          for(int i=0; i<N; i++)
          {
               if ((s & (1 << i)) != 0)  //proveruvame dali i-tiot bit vo 's' e 1
               {
                    currentWeight += weight[i];
                    currentValue += value[i];
               }
          }
          
          if(currentWeight <= C)        //gi sobira vo ranecot
          {
               bestValue = max(bestValue, currentValue);
          }
     }
     
     return bestValue;
}

Доколку, покрај најдобрата вредност, сакаме да го зачуваме и самиот избор на предмети кој води до таа вредност (кои предмети треба да ги земеме во ранецот), можеме истите да ги чуваме во низа со динамичка големина. За да знаеме, кај едно подмножество, кои елементи треба да ги додадеме во низата, потребно е само да забележиме што се случува во делот каде што ги зголемуваме currentWeight и currentValue. Имено, веднаш се забележува дека тој е делот каде што проверуваме кои од N-те елементи се наоѓаат во подмножеството кое го разгледуваме во дадениот момент.

Како што можете да забележите, самото решение е едноставно за разбирање и лесно за пишување. Сепак, најчесто, кога за една задача постојат повеќе решенија (како на пример, кај проблемот на ранец веќе разгледавме и решение со динамичко програмирање), ова решение базирано на испитување на сите подмножества ќе биде побавно. Од друга страна пак, постојат ситуации каде што е сложено да напишеме програма која користи динамичко програмирање за решавање на проблемот на ранец - на пример, што доколку тежините се реални броеви (во тој случај, не можеме да користиме низа за чување на најдобрите решенија за помалите подпроблеми, што ни е важен дел кај алгоритмите кои се базираат на техниката на динамичко програмирање). Слично, доколку имаме мал број на предмети, решението базирано на разгледување на сите подмножества е најчесто поедноставно за пишување - како што можете да видите погоре. Накратко, за секој проблем, потребно е да знаеме што точно се бара од нас, како и кои се ограничувањата во однос на бројот на елементи и слично, пред да одбереме кој алгоритам е посоодветен.

Во однос на постапката која ја разгледавме во ова предавање (создавањето на сите подмножества), истата можеме да ја користиме во ситуации кога имаме до (отприлика) 20-25 елементи, бидејќи има околу милион подмножества од 20 елементи (220 = 1048576). Сепак, постојат многу проблеми каде што имаме ваков мал број на елементи (има помалку од 20 големи градови во Македонија, помалку од 20 министри во Владата, итн), па оваа техника на решавање може да се примени кај некој проблем поврзан со истите. Слично, кога имаме потешкотии со смислување на решение на некој покомплициран проблем, можеме да ја искористиме оваа идеја на разгледување на сите подмножества за да забележиме некоја поврзаност помеѓу решенијата (на пример, можеби ќе забележиме дека сите решенија се парни броеви, или дека секогаш постои решение кое мора да поминува покрај некој град, итн).

За крај, запаметете дека постојат повеќе проблеми кои може да се решат со разгледување на подмножествата од елементите кои ни се дадени на располагање. Сепак, важно е да наведеме дека кај проблемите кои ќе ги решавате, потребно е да има релативно мал број на можни елементи (на пример, 20тина), и, при разгледувањето, да не е важен распоредот на елементите (на пример, кај проблемот на ранец, не е важно дали прво ќе се стави лаптоп па книга, или пак обратно – книга, па лаптоп). Причината за второто ограничување е јасна - постои само едно подмножество каде се разгледуваат тие елементи - па, на пример, кога имаме три елементи ги разгледуваме само следните опции: {}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}, и, како што можете да видите, разгледуваме опција {0, 2}, но не и {2, 0}.

Дозвола за користење: CC BY-NC 2.5 ©