Ahoj, potrebujem naprogramovat problem batohu, a chcel by som sa spytat na dve veci. Prva vec, aky datovy typ vyzera byt najvhodnejsi na ukladanie jednotlivych poloziek (programujem v C++)? Druha otazka, robim zatial len brute force, mozno sa budem za to pri citani odpovedi hanbit (myslim si, ze to bude primitivne), ale teraz nejak neviem prist na nejake rozumne riesenie, ako prejst vsetky mozne kombinacie jednotlivych poloziek. Problem mam s tym, ze ak mam napr 5 poloziek, tak potrebujem skontrolovat aj kombinacie po dvoch, ale aj po 3, 4 atd, a to nejak neviem vymysliet. Vedel by mi niekto poradit? Dakujem.

uplne primitivne to nie je, problem batohu je np uplny a nejestvuje polynomialny algoritmus, ktory by pre vseobecne zadanie vedel vzdy najst optimalne riesenie. riesenie sa da najst dynamickym programovanim. ak pogooglis problem batohu alebo knapsack problem, tak najdes urcite algoritmus a mozno aj implementaciu v c++
PS: aby si sa vyhol terminologickym fópá... programujes algoritmus, ktory riesi problem, neprogramujes problem

Ahoj, dakujem za odpoved. Ano, dynamickym programovanim to budem riesit neskor, teraz to vsak potrebujem ciste len bruteforcom, a rozmyslam nad tym, ako to napisat tak, aby bola vysledna zlozitost 2^n. Nasiel som par kodov, napr tento https://stackoverflow.com/questions/233 ... rute-force ale nechapem, preco tam pridava do pola A premennu k, ktoru nasledni deli a moduli.

Kod 'j' cyklu si mozes predstavit ako binarne pocitadlo, kde pocet bitov sa rovna size. (pocet moznych kombinacii sa rovna 2^size). Vo vysledku sa v A objavi 0 alebo 1, kde 1 znamena ze polozka sa skusi pridat do batoha.

Premenna 'k' funguje ako priznak, ze sa ma v dalsom rade pripocitat 1 (po anglicky carry). Dolezite je si uvedomit ze v A budu len 0 a 1