PROBLÉM SOUČTU PODMNOŽIN
ALGORITMUS ŘEŠENÍ "NA HRUBO"

---

PROBLÉM

Chceme najít podmnožinu množiny A.1,...,A.N, jejíž součet je největší možný, ale ne větší než T (T je tzv. velikost batohu).

ALGORITMUS

Algoritmus řešení "na hrubo" (Greedy algorithm) zkoumá prvky vstupního pole a každý, který se ještě "vejde do batohu" je uznán jako prvek hledané podmnožiny. To je samozřejmě rychlé, časová složitost je O(N*lgN) vzhledem k doporučení vstupní hodnoty nejprve utřídit na nerostoucí posloupnost, a samozřejmě nepřesné. Martello a Toth pro vyjádření přesnosti přibližného řešení aloritmem A. definují číslo R.A takto: Nechť A. je aproximační algoritmus pro daný (maximalizační) problém. Pro konkrétní instanci I tohoto problému označme OPT.I optimální hodnotu řešení a A.I hodnotu nalezenou algoritmem A.; pak číslo R.A pro daný algoritmus A. je definováno jako největší reálné číslo R.A takové, že platí

(A.I/OPT.I)>=R.A pro všechny instance I

Číslo R pro algoritmus řešení "na hrubo" je rovno 1/2.

IMPLEMENTACE

Jednotka: vnitřní podprogram
 
Globální proměnné: pole A.1,...,A.N přirozených čísel, výstupní pole X.
 
Parametry: přirozené číslo N, přirozené číslo T
 
Vazby: D_QUICKSORT - třídění do nerostoucí posloupnosti
 
Výsledek: výstupní pole X., pro každé J=1,...,N platí: X.J=1, jestliže prvek A.J patří do hledané podmnožiny, X.J=0 jinak

GS: procedure expose A. X. parse arg N, T call D_QUICKSORT N X. = 1 do J = 1 to N   if A.J > T then X.J = 0; else T = T - A.J end return

Seed = RANDOM(1, 1, 481989) do J = 1 to N   A.J = RANDOM(1, 1000) end

Součet podmnožin - porovnání algoritmů
Algoritmus	Suma prvků	Sekund
GS	25554	0.05
DPS	25557	240.24
APPROX_SUBSET_SUM	25436	12.31
DIOPHANT	25557	0.82