Generátor instancí problému batohu

Výkon některých algoritmů (rychlost nebo kvalita řešení) může být ovlivněn statistickými parametry generovaných instancí.

Cena

Instance nikdy neobsahuje dvě věci téže váhy (dominance). Cena je v zadaném rozsahu rovnoměrně rozložena.

Poměr kapacity batohu k sumární váze

Optimální řešení se může skládat z několika málo věcí nebo z téměř všech věcí. Podle toho, "z které strany" řešení hledáme, můžeme prozkoumat větší nebo menší část stavů. Pro poměr větší než jedna je pochopitelně řešením soubor všech věcí. Zadáme-li maximální váhu věci a rozložení (granularitu), je tím (statisticky) určena i sumární váha. Proto kapacitu batohu určujeme nepřímo, poměrem k sumární váze.

Granularita

Je možno ovlivnit, zda instance bude obsahovat spíše malé nebo spíše velké věci. Pro převahu malých věcí je pravděpodobnost, že věc s váhou w bude v instanci zahrnuta

p=1/w^k,

kde k je volitelný exponent. Pro převahu velkých věcí platí symetrický vztah

p=1/(w_max-w)^k.

Zdrojové texty generátoru

Pokud chcete provozovat generátor lokálně nebo získat jinak parametrizované instance, je zde k dispozici verze pro příkazovou řádku. Původně byla přeložena gcc 2.7.2, měl by vyhovět jakýkoli ANSI C překladač. Pro sestavení je potřeba knihovna matematických funkcí libm (parametr -lmpro gcca jiné překladače).

`knapcore.c`	funkce `knapcore` vygeneruje jednu instanci do připravených polí pro váhu a cenu
`knapcore.h`	prototyp funkce `knapcore`
`knapgen.c`	hlavní funkce pro `knapcore`, parametry se berou z příkazové řádky

Řízení granularity je implementováno zcela přímočaře. Věc s rovnoměrně náhodně vygenerovanou vahou se přijme nebo odmítne v závislosti na prahu odvozeném od váhy a dalším náhodném čísle. Je to jednoduché, ale při větších exponentech to generátor citelně zpomaluje (mnoho odmítnutých věcí).

Pro ty, kdo by se chtěli podobnými generátory zabývat více, uvedu víceméně standardní techniku:

Předpokládejme, že máme generovat náhodná čísla s rozložením f(x).
Odvodíme funkci g(x) jako integrál f(x).
Odvodíme inverzní funkci g^-¹(x).
Výstup standardního generátoru náhodných čísel transformujeme touto funkcí.

Analytické odvození g^-1(x) nemusí být snadné nebo dokonce možné. Pro jednoduché tvary závislostí užitých v generátoru by se to provést dalo, pro exponenty blízké 1 nemusí být metoda numericky spolehlivá.

Velikost instance (celé číslo)
Počet instancí (celé číslo)
Maximální váha věci (celé číslo)
Maximální cena věci (celé číslo)
Poměr kapacity batohu k sumární váze (desetinné číslo)
Charakter granularity	Více malých věcí Více velkých věcí Nerozlišovat
Exponent závislosti granularity (desetinné číslo)