[OT] Jak narezat trubky?

[Ales Prochaska]

Neni to tak zle. Tohle jsem jednou resil (a zdrojak nemuzu najit,
jinak bych to poslal). Algoritmus jsem si "vycucal z prstu", nejak se
tam nahodne sestavovaly ty prirezy a kdyz byl jeden polotovar skoro
dobre tak se slo na dalsi, kdyz se to nedarilo tak se nejaky nahodne
rozboural a zkouselo se to jinak. Obvykle se behem par vterin az minut
naslo prijatelne reseni velmi blizke optimalnimu a vyrazne lepsi nez
co byli schopni rucne sestavit na dilne. A taky slo o desitky tyci a
stovky prirezu.

Ales Prochaska

>> 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
>> 

> _______________________________________________
> HW-list mailing list  -  sponsored by www.HW.cz
> Hw-list na list.hw.cz
> http://list.hw.cz/mailman/listinfo/hw-list