Matematické Fórum

Těžko ti pomoci, já zadání vůbec nerozumím.

Pořád nerozumím. Zkus uvést příklad. A nemícháš dohromady pojmy číslo a číslice?

↑ neznalek11:
Takže korunový problém? Máš x bankovek/mincí a potřebuješ najít takovou kombinaci těch bankovek a mincí, abys získal nějakou určitou sumu?
Případně máš množinu A, která obsahuje n čísel a ty máš zjistit, která podmnožina A' z množiny A má součet svých členů rovný X?

Takhle nějak je to zadání? :-)

Naznačím postup, kterým by to řešil program. Řekněme, že
máme čísla 2,3,5,7,11,13,17,19 (i-té označme a_i) a chceme dosáhnout sumu 34. Program si vyrobí pole celých čísel indexované od 0 do 34. Na začátku budou všechny krom nulté rovny -1, nultá bude rovna 0. Program provede tolik kroků, kolik je zadaných čísel. V i-tém  kroku uloži a_i na pozici j, pokud je možné dosáhnout součet j pomocí prvních i hodnot a hodnota a_i přitom musí být využita. V prvním kroku tedy akorát nastaví druhou hodnotu na 2 (součty dosažitelné pomocí hodnoty 2 jsou pouze 0 a 2). Ve druhém kroku uloží číslo 3 na pozice 3 a 5 (3 a 5=3+2 lze získat pouze použitím 5). Obecně lze říct, že v i-tém kroku se program podívá, kde byla v předchozím kroku nezáporná čísla, posune se od toho místa o a_i pozic doprava a pokud tam je -1, uloží tam a_i. Pole je přitom lepší procházet odzadu, vyhneme se tak testům, jestli jsme k dosažení příslušného součtu už a_i nepoužili.

Na konci se podíváme, co je v poli uloženo na 34. pozici. Pokud -1, součet dosáhnout nelze. Pokud kladné číslo, víme, jakou hodnotu jsme přidali jako poslední. Tu od součtu odečteme, dostaneme mezisoučet m. Zjistíme, jaké číslo je na m-té pozici, to jsme získali k dosažení součtu m. Takto postupujeme dál.

Složitost algoritmu je n*M, kde n je počet hodnot a M zadaná suma. Pro velké sumy všechny známé algoritmy selhávají, věří se, že žádný efektivní neexistuje (resp. toto je ekvivalentní s jedním z nejznámějších otevřených problému -- P=NP).

Při řešení na papíře lze postupovat obdobně, místo celého pole si můžeme psát pouze dosažitelné součty a mezi nimi šipky, které nám určí, jak jsme se ke kterému součtu dostali.