2. Fórumok
  3. Szoftverfejlesztés
  4. Programozás topic
  5. (kiemelt téma)
Keresés

Új hozzászólás Aktív témák

  • #14431 bambano titán zsolti_20 #14423
    Új Válasz #14431
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    bambano

    titán

    válasz zsolti_20 #14423 üzenetére

    pakolási problémának hívják az operációkutatás témában.
    az eredeti pakolási probléma szerint van n darab tárgyad, mérete ismert, amit minél kevesebb sztenderd dobozba kell beleraknod.
    bebizonyítható, hogy az alábbi algoritmus max. 1 dobozzal kér többet, mint az elvi optimum.
    méret szerint csökkenő sorrendbe rakod a tárgyaidat, és mindegyiket belepróbálod először az első dobozba, utána a másodikba, harmadikba, stb. és belerakod a legkisebb sorszámúba, amibe belefér.

    ezt a problémát és megoldást át lehet faragni a te feladatodra, mint ahogy opr tapogatózott is a helyes irány felé.

    szerk: azon még egy kicsit túráztatom az agyam, hogy szimplex módszerbe bele lehet-e erőszakolni. mondjuk favágó módon az összes operációkutatási alapfeladat visszavezethető szimplex módszerre, csak lehet, hogy nem fog beférni a memóriádba :)

    szerk2: Lovász-Gács Algoritmusok és Peter Henrici Numerikus analízis könyve jól jöhet.

  • #14430 opr nagyúr zsolti_20 #14423
    Új Válasz #14430
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    opr

    nagyúr

    válasz zsolti_20 #14423 üzenetére

    Erre nem letezik tokeletes algoritmus sajnos. Idealishoz kozeliteni tudsz, de elerni soha nem fogod, hacsak nem mesz vegig az osszes permutacion.
    Innentol kezdve tobb megkozelites lehetseges, leirom amik igy hirtelen eszembe jutnak, biztos lehet ezeknel jobb/optimalisabb megoldast is talalni, ha kicsit tovabb gondolkozunk.

    Kapasbol kerdes, hogy ebbe a listaba csak olyan megrendelesek kerulnek-e bele, amik onmagukban teljesithetoek.
    Ha nem, akkor ez lenne az elso szurom.

    Ha mar van olyan lista, amiben csak a pillanatnyilag teljesitheto megrendelesek vannak, akkor a kovetkezo kerdes az, hogy a sulyozas kizarolag a kikuldott csomagok mennyisege, vagy mas szempont is (pl rendelesi ertek, rendelesi/varakozasi ido, stb).

    Ha csak a csomagok szamossaga, akkor:
    a) megoldas: csinalunk egy uj oszlopot, amiben osszegszeruen szerepel a megrendelt dolgok darabszama, tehat 1-1-1-1-2 eseten az, hogy 6. Ezek utan ilyen teren novekvo sorrendben vegig lehet menni a rendeleseken, es a teljesithetoeket berakni a "kosarba". Ha valamibol elfogy az, ami raktaron van, akkor onnantol ha olyan rendelesbe botlunk, amibe kene olyan is, ugrunk tovabb.
    Van tobb buktatoja a dolognak, de alapvetoen mukodokepes lehet, ha mellette bevezettek valami extra kriteriumot, hogy x ideje bent allo rendeles top prioritast kap vagy ilyesmi.
    b) megoldas: hasonlo az A-hoz, annyi, hogy minden rendeles utan csinalsz egy meg teljesitheto rendeles tablat, es ezen mesz vegig.

    De oszinten szolva -bar so-so mukodnek- ez mind szar megoldas. Ennel jobb megoldas az, hogyha a raktarkeszlet rendelesfuggoen szepen okosan vezetve van, es olyan dolog, amibol mar tobb rendeles nem teljesitheto, vagy nem rendelheto, vagy ki van irva, hogy elfogyott es rendelni/gyartani kell belole. Es akkor nem kell szivni megoldhatatlan problemakkal sem. :D

    En azt szoktam mondani, hogyha olyan problemara, aminel nem biztos, hogy ez indokolt, bonyolult algoritmus kell, akkor lepj egyet hatra es gondold ujra, mert nagyon valoszinu, hogy valami mar regen el van b@szva, es inkabb azt kene kijavitani.

    Sok sikert! :R

  • #14428 axioma veterán zsolti_20 #14423
    Új Válasz #14428
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    axioma

    veterán

    válasz zsolti_20 #14423 üzenetére

    Lassu voltam, a tied volt az utolso mikor kezdtem, akkor a nagy resze felejtos.
    Amugy meg tuti hogy a legjobb jo csak neked? Es biztos hogy nem lehet jo kozelitest adni pl. azzal hogy melyik csomag a "legolcsobb" (itt azt ertve alatta, hogy vagy az hogy a legkevesebb darab kell bele, vagy az hogy legkevesebb "kiegeszites" kell neki, amit a rendelkezesre allo atlag darabszamtol valo kulonbseget ertem elojelesen)? Es biztos hogy nem az eladott aruk mennyiseg a legjobb mertek?

    Felteszem oktatasi kerdes, mert amugy hulyeseg lenne minel tobb csomagrol darabszamban beszelni. Akkor meg gyanithatoan egy operaciokutatasos (mashol linearis programozasnak is hivjak) feladat mintapeldaja. [Es most pongyolaba valtok at mert 20 eve volt...] Valtozoi: x_i jelenti hogy az i. csomagbol mennyi lesz (felteszem ez 0-1), bal oldalak transzponalva ez a tablazat (x_1*[A az 1-ben]+...+ <=osszA stb.), valamint az x_i<=1 feltetelek, celfuggveny sum(x_i)->max. [Megjegyzem, amit az alap simplex modszer nem old meg, az kodolasilag szivas, de azt azert en inkabb megkeresnem hogy hol milyen lib-ben van meg es lehet instant modon felhasznalni.]

  • #14427 Ispy nagyúr zsolti_20 #14423
    Új Válasz #14427
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    Ispy

    nagyúr

    válasz zsolti_20 #14423 üzenetére

    Először meghatároznám a kombinációkat, amik kijöhetnek a 10 rendelésből, utána kiszámolnám, hogy az egyes kombinációk esetében melyik cikkből mennyi darab jön össze, azokat kiejteném, ahol valamelyik cikkszám meghaladja a készleten lévő mennyiséget, a maradékból pedig azok a kombók, ahol a legtöbb az elemek száma.

    Ebből a legbonyibb a kombinációk számosságának a meghatározása, ezt egy db-ben letárolnám, hogy első: 1, második: 1,2 stb. a többi már szimpla adatbáziskezelés, pár update, meg sum, meg select.

  • #14426 Silεncε őstag zsolti_20 #14423
    Új Válasz #14426
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    Silεncε

    őstag

    válasz zsolti_20 #14423 üzenetére

    szerk: semmi, nem jót mondtam

  • #14424 dabadab titán zsolti_20 #14423
    Új Válasz #14424
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    dabadab

    titán

    válasz zsolti_20 #14423 üzenetére

    Van tíz rendelésed, vagyis összesen 1024 kombináció, azt fél lábon állva is végig lehet próbálgatni :)

Új hozzászólás Aktív témák

Hirdetés