Verovatno varjanta "Problema ranca" (knapsack problem)

Molim bilo kakvu vrstu pomoći oko sledećeg problema:

Radi se o optimizaciji rezanja materijala (šipki) koje imaju određenu dužinu npr. 6000 mm. U krojnoj listi dobijam n-broj delova različite dužine (koji su manji od dužine šipki od koji se režu() koje treba iseći od osnovnih šipki. Problem je rešiti kako da ima što manje otpada tj. što bolje uklopiti delove prilikom rezanja.

Pretražujući forum (koji inače ne pratim) našao sam da moj problem je verovatno neka verzija KNAPSACK problema. Program inače radim u VB6. Bilo kakva pomoć bi dobrodošla.

A koliko tih osnovnih "shipki" imash? I ako ih imash vishe, jesu li sve iste duzine, ili su razlichite?

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Osnovne šipke su ulazni materijal i uvek su iste dužine (6000 mm). Mogu ih "potrošiti" onoliko koliko je potrebno da se iskroji odredjena narudžbenica. Npr. u listi za sečenje imam zadatak da se iseku delovi šipki sledećih dimenzija (dužina):
3 x 1200 mm, 6 x 950 mm, 8 x 1345 mm, 3 x 1100 mm.(ove vrednosti su proizvoljne i u pogledu količine i dimenzija za svaku naružbenicu ali uvek su manji od 6000 mm)

- Dalje je potrebno izračunati kojim redom poslagati delove za sečenje a da prilikom sečenja od osnovnih šipki ne ostaje ostatak manji od 600 mm (takav ostatak je škart koji se ne može ponovo upotrebiti)
- pri izračunavanju nije bitno koliko će osnovnih šipki biti utrošeno za isecanje potrebnih delova.
- Ukoliko je pri uklapanju odredjenog broja delova ostatak na jednoj osnovnoj šipki (od 6000 mm) recimo od 0 mm do 100 mm, na njoj je idealno uklopljeno rezanje.
- Ukoliko je ostatak od 100 mm do 600 mm takvo uklapanje je neprihvatljivo jer deo koji ostaje je za kasnije ne upotrebljiv.
- Ukoliko je ostatak od 600 mm do < od najmanjeg dela za sečenje u navedenoj poružbenici on je prihvatljiv jer će se upotrebiti prilikom neke sledeće naružbenice.

Ukoliko je komplikovano - jednostavnija postavka je n- broj delova proizvoljnih dužina uklopiti sa što manjim ostatkom na x-broj osnovni šipki konstantne dužine od 6000 mm.

Unapred hvala za pomoć

Ako je broj duzina koje se trebaju dobiti mali, onda mozesh da problem reshish i bektrekom.
Resenje dinamickim programiranjem bi moglo da ide ovako:

neka nam je N broj ulaznih shipki (sa n cemo obelezavati njihovu duzinu), a M broj
trazenih duzina. Neka X_i, i=1..M, je i-ta trazena duzina. Neka V[i,k,j] znachi da
popunjavamo prvih i shipki, sa prvih j duzina, tako da nam je u i-toj shipki popunjeno k
mesta. V[i,k,j] moze imati vrednost 0(sto znaci da smo sve sipke od 1 do i-1 popunili sa
zadovoljavajucim ostatkom) ili 1(sto znaci da smo popunjavajuci neke od shipki dobili
nezadovoljavajuci ostatak ili nismo uopste stigli do ovakve situacije). Ako nam je
poznato neko V[i,k,j], mi mozemo izracunati i sledece vrednosti:

ako je v[i,j,k]=0 i k<100 ili k>600 onda v[i+1,x[j],j+1]:=v[i,j,k];
ako je v[i,j,k]=0 i k>=x[j] onda v[i,k-x[j],j+1]:=v[i,j,k];

Na pocetku postavish vrednost V[1,n,0]:=0, i redom popunjavash. Na kraju pogledash
koja od vrednosti V[N,k,M], k=0..200, 600... ima vrednost 0, i na osnovu nje
rekonstruishesh gde si koju duzinu sekao.


Ovo moze lako da se prosiri tako da dobijesh reshenje koje ce ti davati i najmanji otpad
(znachi od svih zadovoljavajucih otpada, dobijash najmanji).
Ako ti neshto nije jasno (ili ako uvidish da sam ja mozda neshto pogreshno napisao),
reci, pa cu probati da razjasnim :)

[edit] I usput sam shvatio da sam, onako, bash lupio :)

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!