Ne zaboravi debljinu reza.

Bas isti zadatak sam resavao na USACO (http://train.usaco.org).
U atachment je tekst zadatka i resenje.

Dobro, debljina reza je po meni trivijalnost kod ovog problema...

Vazan mi je algoritam, mozda ne i algoritam nego sam pristup problemu ;)

Pa sta je, zar se niko nije bavio ovim problemom?

sta je optimalno iskoriscenje?

Pod optimalnim iskoriscenjem se podrazumeva da uradis takvu(e) kombinaciju(e) elemenata, da imas sto manji otpad.
Npr.
duzina elemenata: 3,4,5,8
duzina sipke: 8

Kombinacija koja nije optimalna je npr:
- na prvu sipku od 8m stavi se: 3+4 (iskoriscenost 7m + 1m otpad) 87%
- na drugu sipku od 8m stavi se: 5 (iskoriscenost 5m + 3m otpad) 62%
- na trecu sipku od 8m stavi se: 8 (iskoriscenost 8m + 0m otpad) 100%
Potroseno je ukupno 3 sipke od 8 metara, iskoriscenost je 20 a otpad su dve sipke od 1m i 3m.
Broj secenja je 2+1=3

Kombinacija koje je optimalnija od prethodne:
- na prvu se stavi: 3+5 (iskoriscenost 8m + 0m otpad) 100%
- na drugu se stavi: 8 (iskoriscenost 8m + 0m otpad) 100%
- na trecu se stavi: 4 (iskoriscenost 4m + 4m otpad) 50%
Potroseno je 3 sipke od 8m, iskoriscenost je 20m, otpad je sipka od 4m.
Broj secenja je 1+0+1=2

Vidi se da je druga kombinacija optimalnija, jer je otpad jedna veca sipka potreban je manji broj rezova...

Ovo je samo neki primer sa malim brojem elemenata, tako da se ovo moze uraditi i rucno. Ukupan broj svih kombinacija je 4!.
Ali kod veceg broja elemenata broj kombinacija naraste id do 30! (za 30 elemenata), tako da brute force bas i nije najzgodniji algoritam za ovaj posao...

Meni se cini da je ovaj problem slican kao knapsack algoritam, sa kojim sam i probao nesto (a verovatno cu i nastaviti), ali ako neko ima neko prostije resenje...

P.S.
Na netu sam pronasao, kod vise izvora, da kod problema gde se broj "resenja" uvecava eksponencijalno, pozeljno je koristiti genetske algoritme (malo teze za implementaciju).

Jos par pitanja... da li mozes da klasifikujes predmete u kategorije .. recimo sve sto se ralikuje za recimo par % stavis u kategoriju sipke duzine 4 +- 2% komada 10 i sl.. pa da umesto sa konkretnim primercima da radis sa kategorijama... nije najoptimalnije ali mislim da ne bi trebalo da % ili %% uticu na kvalitet algoritma... isto tako ako bi recimo sklapao sipke na osnovu kategoria mogao bi da primenis foru iz nekog algoritma za nalazenje minimalnog rasplinuceg stabla... fora je valjda da ako odaberes kombinaciju koja daje najmanju gresku od svih ostalih onda ona ulazi u krajnje resenje.. problem je kako je pronaci.. mozda ukoliko bi resenje trazio po intervalima .. recimo nadji sva resenja koja imaju gresku manju od 1%.. ako je samo jedno onda ga prihvati ako ih ima vise onda ih trazi polovljenjem intervala...

ja nisam neki programer sto se tice ovakvih zezancija.. nadam se da nisam previse lupao... ako jesam ne zamerite mi .. pozdrav...

Moze se reshiti i linearnim programiranjem (operaciona istrazivanja).

Kao sto je neko ovde naveo i meni ovo mnogo vise lici na problem ranca.

A ukoliko te zainteresuje problem pakovanja i secenja preporucio bih ti da pogledas nesto o linearnom programiranju, genetskim i algoritmima simuliranog kaljenja