[OT] Jak narezat trubky?

Slavomir Skopalik skopalik na elektlabs.cz
Středa Leden 26 15:48:30 CET 2011


> Jste si jisty? Podle me staci O(n^k). Nepotrebuju zkouset 
> vsechny permutace, ale staci mi treba nerostouci delka kusu 
> (prehazeni mi nic
> neprinese)

Ano zde mate pravdu.

> Takze n moznosti pro umisteni hranice kousku dane delky (n = 
> delka tyce/delka kousku), k typu kousku Kdyz nad tim 
> premyslim, dobre by se to nejspis psalo v prologu :)

Obavam se, ze na skutecne ulohy (tj, treba 20+ ruznych delek, kazda v ruznem
mnozstvi,
celkem rekneme spotreba 20 tyci) to proste hrubou silou nedate.
A pokud hrubou silu, tak urcite kompilovany jazyk a velmi dobre
optimalizace.
Na druhou stranu, pro otestovani algoritmu je to lepsi nez C/C++ :).

A ted jedna zakerna uloha na zaver:

4m tyc.
Narezat:
8x 3.3m
8x 0.5 m

A co je lepsi, 8x 0.2 m zbytek z 8 tyci, nebo 8x 0.7 zbytek z 10 tyci
(rozhodnuti, zda jde o zbytek, nebo odpad neni vzdy zcela jednoduche).
Dalsi slozitost tomu muzete pridat tim, ze tyce nebudou mit 4m, ale bude se
jednat i o zbytky z minula.

Slavek

> 
> KR
> 
> 2011/1/26 Slavomir Skopalik <skopalik na elektlabs.cz>:
> > "Vyzkouset vsechny moznosti" jde i pri dnesnim vykonu CPU jen pro 
> > velmi male, prakticky jen skolni ulohy, protoze slozitost roste s 
> > faktorialem.
> _______________________________________________
> HW-list mailing list  -  sponsored by www.HW.cz 
> Hw-list na list.hw.cz http://list.hw.cz/mailman/listinfo/hw-list
> 



Další informace o konferenci Hw-list