[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