Kábelvágási probléma

Algoritmusok

Sziasztok,

A következő problémára szeretnék hatékony algoritmust találni:
- Adott több, különböző méretű kábel darab (pl: 1m, 3m, 4m, 5m, 32m, 47m, 57m, 500m, stb.)
- Adott több, különböző méretű kábel igény (pl: 45m, 100m, 110m, 18500m, stb.)

A cél az lenne, hogy megkeressük a legpontosabb egyezést, azaz ne vágjunk kábeldarabot további darabokra, ha van a kábel daraboknak olyan csoportja, amelynek összege kiadja a kábel igényt. Az igényt azonban minden esetben teljesíteni kell, tehát a kábelek darabolása néha elkerülhetetlen.
A jelenlegi megoldásomban azt vizsgálom, hogy x db tetszőleges szám összege ad-e pontos egyezést valamelyik kábelre, amiben x-et 1-től indulva folyamatosan növelem.
A problémám, hogy már 10 alatti x esetén is elérem a gép memóriájának határait és a futási sebesség is percekben mérhető (a kábel darabok száma és az igények száma is 100 feletti).

Előre is köszönöm a javaslatokat!

( joco01 v | 2015. 05. 05., k – 18:53 )

A feladat így nem elég pontos, előbb definiáld, hogy milyen kritériumra kell optimalizálni. Azt tudjuk, hogy a szélsőérték az, ha nem kell semennyiszer vágni. De ha kell vágni, akkor hogyan értékeljük?

Ha például a legvégén 1+4 méter kimarad, az jobb vagy rosszabb, mintha 2+3 méter marad ki? Később lehet, hogy a maradékokat is fel kell használni, tehát nem dobódik ki, vagy de? Vagy az a fontos, hogy minél kevesebb darab vágás történjen, és mindegy, hogy milyen hosszok mentén?

--

Azt kene inkabb menedzselni hogy minel kevesebb olyan maradek maradjon amit kesobb nem lehet eladni mert ritka mint a feher hollo pl 1M alatti vagy mit tudom en.
Tehat ha kisebb lenne a maradek egy 5 meteres rendeles miatt mint az altalanos megrendelesekben eladhato ( ide felvenni a gyakori megrendeleseket x y z meretek ) akkor inkabb kezdjenek uj kabelt.

Hmm de csak van megrendelesi statisztikatok hogy miket rendelnek. Most is irtad 1 metertol x kilometerig.
1M alatt nincs? Akkor nem szabad olyat vagni ami ala esne. Es igy tovabb felfele lehetne megnezni hogy peldaul ha kabel hossza beesik 20 meter ala abbol csak 1 evben egyszer rendelnek.
Persze azt is meg kell nezni mennyi helyetek van ha esetleg raktarozni kell ami esetleg tobbe kerul mintha kidobod azt a 30 cm-t a vegen ( ha ebbol sok van akkor erdemes azzal foglalkozni amit irtam )

Van statisztikánk, de a beépítési területtől és a kábel típusától függ a kábelhossz.
Ha a múltban sokszor is rendeltek egy adott méretet, nincs rá semmi garancia, hogy ez megismétlődik. Ezen felül az algoritmusnak a kábeltípustól függetlenül kellene működnie a jövőbeni típusokra is.

Magyarul egy cél van, a kimaradó darabok minél nagyobbak legyenek. Vagyis ha nem marad ki semmi, az a legjobb.

Azt írtad, hogy a darabok is és az igények is különbözőek. Ez biztos? Nem tűnik életszerűnek.

Mi van akkor, ha van X darab kábel, Y darab igény, és ki lehet őket elégíteni őket valahogyan a szempontok szerint legjobban, utána másnap bejön egy Y+1-edik igény, ami miatt tegnap mégis csak jobb lett volna máshogy vágni? Reméljük a legjobbakat, és nem kell vele foglalkozni?

--

Magyarul egy cél van, a kimaradó darabok minél nagyobbak legyenek. Vagyis ha nem marad ki semmi, az a legjobb.
Így van, erre kellene egy hatékony algoritmus...

Azt írtad, hogy a darabok is és az igények is különbözőek. Ez biztos? Nem tűnik életszerűnek.
Biztos, hogy különbözőek. Több fajta kábel van, némelyik 100, 200, 500, 1000m-es dobon érkezik. Van a múltból rengeteg kisebb darabunk is, amit el kellene használni.
Csak adott napi igényekkel számolunk, a hosszú távú tervezést más program végzi, és az alapján húzza be az új dobokat.
Az az egy tényező garantált, hogy az adott napra szükséges méternyi kábel legalább 10% biztonsági ráhagyással rendelkezésre áll.

... másnap bejön egy Y+1-edik igény, ami miatt tegnap mégis csak jobb lett volna máshogy vágni? Reméljük a legjobbakat, és nem kell vele foglalkozni?
Jelenleg azt szeretném elérni, hogy az aznapi vágásokat ki tudjam számolni maximum 10 percen belül. Ha sikerül elég hatékony algoritmust találni, ami 1-2 percen belül elfogadható eredményt ad, akkor lesz még 8 perc, amit ennek optimalizálására szánhat...

A különböző alatt ezt értettem: létezik-e, hogy van 2 darab egyforma hosszú igény, vagy 2 darab egyforma hosszú kábel a raktárban? Mert ennek az ellenkezője nem életszerű.

Másrészt azt sem tartom életszerűnek, hogy 17 darab 1 méteres kábelből raksz össze egy 17 méteres igényt. Pedig egy algoritmusnak nagyon csábító lenne a maradékok ily módon való felhasználása. Milyen kábel ez egyáltalán?

--

( bazso | 2015. 05. 05., k – 21:01 )

?

"kábel daraboknak olyan csoportja, amelynek összege kiadja a kábel igényt"

Azaz ha akarok venni nálatok 10m kábelt, akkor adtok egy adag felszecskázott darabot és kötögessem össze? :D

Ezt a része bezavar a megoldásba, mire gondoltál itt valójában?

( bazso | 2015. 05. 05., k – 21:35 )

Azzal mi a gond, hogy a legkevésbé szimpatikus ügyfél/dolgozó igényét a raktárban található darab kábelekkel elégíted ki, lehetőleg a legkisebbtől kiindulva, hogy megszabadulj a legproblémásabb daraboktól, majd az esetlegesen hiányzó részt egy lehetőleg megkezdett dobból vágod le oly módon, hogy minimum a dob kapacitásának a fele megmaradjon? Ha ez nem megoldható, akkor akár 2 dobot is megkezdhetsz neki, a lényeg, hogy a maradék minél használhatóbb legyen.
Ezzel egy tranzakció során megszabadulsz egy rakás darabtól, míg keletkezik új max 2.

( lx | 2015. 05. 05., k – 21:43 )

Készítsd el a klasszikus pénzcímletező algoritmust.
Ha azzal elkészültél, készen lesz ez is.

( arpi_esp v | 2015. 05. 05., k – 21:48 )

milyen kabel lehet az amibol 1m es 18km is hasznalhato valamire? :)

a problemara: en elso korben kizarnam a hosszabb igenyeket, itt kicsi az eselye hogy maradekbol megoldhato, masreszt a kabel aran levo haszon fedezi a veszteseget ugyis.

utana elindulnek a leghosszabb igenytol lefele, megneznem van-e egyaltalan olyan hulladek ami ennel hosszabb, ha igen, akkor probalnek keresni hozza a rovid igenyekbol part ami egyutt kiadja valamelyik hulladek hosszat. ezt lehet mondjuk 3-5 kabelig novelni, az meg nem veszes szamolas.
es igy haladni az egyre rovidebb igenyek fele, mivel ott nagyobb az esely hogy valamelyik maradekbol meg kijon. persze ez nem ad tokeletes eredmenyt, de relative jo lehet.

amugy a statisztikat sem vetnem el, persze nem garancia semmire a multbeli igenyek, de azert jo tampontot adhat. ez alapjan lehetne sulyozni a hibakat.