Hogyan lehet megoldani a problémát, hogy megváltoztassák a minimális számú érmék nagy számban kötegtúlcsordulást on

Megoldja a problémát a kis érméket. Alábbi feltételek szerint. A probléma az, hogy az összes megoldást, amit eddig tapasztaltam, hogy egy csomó memóriát. Nem alkalmazható nagy bemenő adatok például az 1 millió 000 A kérdés az, hogy hogyan tudjuk optimalizálni megoldások a nagy számok? Vagy talán van valami hatékonyabb ötlet, hogy megoldja ezt a problémát?

Szerint a számok és 1≤n≤30 1≤w≤10 ^ 9, és egy sor számok 1≤v [1], ..., V [n] ≤10 ^ 9 megtalálják a minimális számú k. amely szám w is képviselteti magát az összege k számokat a készlet. Minden szám a készlet használható tetszőleges számú alkalommal. Köztudott, hogy a csomag egy egységet, és hogy minden számpár a készlet egyikük osztható másik. Ez garantálja, hogy az optimális válasz a kifejezések száma nem haladja meg a 10 ^ 4.

Nyomtató k és a feltételek magukat.

Köztes tömböket nem kell:

Annak a ténynek köszönhetően, hogy mindig célérték osztva a lehető legmagasabb, eredmény mindig növekszik a lehető legkevesebb. A végén már 1 feltétel.

A listát a kiválasztott érmék közé tartoznak azok, amelyek kevesebb, mint az előirányzott összeget cél - csak kisebb érme, így ő lehet cserélni.

Miért van szükség az algoritmus a legjobb megoldás? Mivel abban az állapotban azt mondják:

bármely két szám a sor egyikük van osztva különböző

Ez azt jelenti, hogy bármennyi beállított oszlik akárhány kisebb első szettet. Tény, hogy az 1. számú előtt a GCD kell az összes szám. Ezért fenntartjuk a jogot arra, hogy rendezni, és cselekedni, mint azt javasoljuk. Ha nem volna egy GCD, akkor igen, arra lenne szükség, hogy rendezni az opciós tőzsdén.

Válaszol december 7 '15 at 09:57