sallle Sasa Ninkovic GTECH Beograd
Član broj: 146 Poruke: 480 *.psit.rs.
ICQ: 20785904
|
eo jednog brut fors pomalo seljackog resenja na prvu loptu:
uzmemo dugovnu stranu, i napravimo sve podskupove dugovanja, i nadjemo vrednosti tih podskupova (vrednost je suma svih elemenata u skupu) - toga ima oko 2^n. Te vrednosti uzmemo i sortiramo i dobijemo uredjen niz - dugovni niz .
Zatim isto uradimo i za potraznu stranu i dobijemo i tu neki uredjen niz sa 2^m clanova - potrazni niz.
Zatim uzmemo maximalni element u potraznom nizu , i pregledamo da li ta vrednost postoji u dugovnom nizu. ako postoji uparili smo citavo potrazivanje. Ako nismo nasli, uzimamo sledeci elemenat iz potraznog niza, i trazimo tu vrednost u dugovnom nizu. itd itd...
primer bi izgledao:
dugovanja: 1,2,4
potrazivanja: 3,1,1
dugovni podskupovi( {1,2,4},{2,4},{1,4},{1,2},{1},{2},{4}). dugovni niz vrednosti: 1,2,3,4,5,6,7
potrazni podskupovi({1,1,3},{1,3},{1,3},{1,1},{1},{1},{3}. potrazni niz vrednosti : 1,1,2,3,4,4,5
uzmemo 5 iz potraznog , i nalazimo tu vrednost u dugovnom:
potrazni elementi: 1,1,3
dugovni elementi: 1,4
(da nismo nasli 5 u dugovnom nizu, probali bi sa 4kom, ... itd).
Svakako da ovo moze da se optimizuje, nadje neki brzi algoritam. al danasnje masine ce lagano da izadju na kraj sa ovim ako je u pitanju 10tak elemenata.
za 20tak i vise, treba smisliti bolji algoritam :)
|