Rjesenje zasnovano na gruboj sili zasnivalo bi se na binarnom broju koji ima onoliko cifara koliko clanova ima niz, gdje 1 znaci da clan ulazi u sumu (a sabiras clanove pocevsi sa jedne "strane" binarnog broja sve dok ne prekoracis zadatu sumu i dok clanovi nisu "potroseni", da ne trosis vrijeme na bespotrebno sabiranje), a 0 da ne ulazi. Svaki put kada nadjes kombinaciju koja daje trazeni zbir, oznacis uzete clanove kao "potrosene". Lose rjesenje, po pitanju vremena izvrsavanja.
Rjesenje zasnovano na backtrack-u je slicno, opet podjes od toga da se prvi clan nalazi u sumi, pa probas sa drugim da se ne ulazi u sumu (druga mogucnost je da ulazi), saberes medjurezultat i ako je prekoracio vracas se unazad jedan korak u rekurziji, ako nije ides dublje u rekurziju, tj. prelazis na sljedeci element u nizu itd. Opet, obiljezavas clanove kao potrosene... Svaki put, kada ulazis u rekurzivni poziv, provjeris da li je element "potrosen", pa ako jeste, ne pravis kombinaciju koja element podrazumijeva kao "ukljucen". Ovo je vec bolje
A to sa threadovima... Kao prvo i C ima threadove, a moje je misljenje da nema smisla uvoditi threadove za ovaj zadatak na jednoprocesorskoj masini
. A moglo bi se paralelizovati, dijeljenjem polaznih pozicija (tj. recimo polaznih pozicija na proizvoljnom nivou rekurzije, nakon odredjenog broja rekurzija izvrsenih od pocetka izvrsavanja) na nezavisne procese, pri cemu je sinhronizacija, naravno, potrebna ali nije problematicna, npr. koristenjem shared memory.
Ono sto mene interesuje jeste da li je ovo dijeljenje na kombinacije jednoznacno? Tj. da li je moguce naci vise setova disjunktnih skupova koji zadovoljavaju postavljene uslove?
Prijavite se
Registruj se
FAQ
Pretraga
