ugrás a tartalomhoz

Hogy mondják angolul?

presidento · 2007. Júl. 19. (Cs), 15.29
Szervusztok.

Van egy algoritmus, amit szeretnék elnevezni szépen (esetleg megtalálni a neten, ki, milyen megoldást adott rá), azonban nem tudom, hogy mondanák angolul. A feladat egyszerű: Adott méretű dobozokba érkeznek különböző méretű dolgok, ezeket kell lehetőleg egyenletesen elosztani, megtartva a sorrendet. (Adott a maximális oldalméret, és nem mutat jól egy teljesen telített oldal, majd utána egy egysoros…)

Például ha a dobozméret 4, az input adatok: 3214312, nem jó módszer, ha mohó módon kiirogatom őket: (32 1 4 31 2), az optimális megoldás: 3 21 4 3 12.

EgyenletesElosztás-ra gondoltam, de biztos van jobb…

Előre is köszönöm a válaszokat és a türelmeteket!
‹ Ami a Jakob Nielsen Web-design könyvet illeti... Eladnám PHP és MySql könyveim ›
 ■
1

knapsack problem

drifter · 2007. Júl. 20. (P), 10.21
A knapsack problem-re gondolsz?

Amúgy itt egy érdekes alkalmazása :)
6

Nem arra gondoltam

presidento · 2007. Júl. 21. (Szo), 19.42
Az nem ugyanaz, hiszen a hátizsák problémában egy halmazt kell kiválasztani, itt viszont az elemek sorrendje fix – az „oldaltöréseket” kell úgy bejelölnöm, hogy lehetőleg ne legyenek nagyon rövid tartalmú oldalak (inkább átlagosan ne töltse ki a rendelkezésre álló helyet).
2

A példát nem egészen értem

zzrek · 2007. Júl. 20. (P), 18.32
Ha a dobozméret 4, és mohó vagy, akkor nem így jönne ki? (3 21 4 31 2) ??
3

Sőt...

vbence · 2007. Júl. 21. (Szo), 11.40
Nem emlékszem már, hogy ez-e a mohó, de ha lerendezed őket nagyság szerint (csökkenőbe), majd sorban bedobálod őket mindig abba, amiben a legkevesebb van:

5 hely esetén

4332211
- - - - -

332211
4 - - - -

32211
4 3 - - -

2211
4 3 3 - -

211
4 3 3 2 -

11
4 3 3 2 2

1
4 3 3 21 2

-
4 3 3 21 21


De ez inkább "paraszti ész" kategória, nagyzolás lenne algoritmusnak nevezni.
5

Az elemek sorrendje fix

presidento · 2007. Júl. 21. (Szo), 19.39
Ez nem jó módszer, hiszen az elemek sorrendjét nem szabad változtatni.
8

Értem...

vbence · 2007. Júl. 21. (Szo), 23.12
Most értettem meg a problémát.
4

A példa rossz

presidento · 2007. Júl. 21. (Szo), 19.32
Elnézést kérek, valóban rossz a példa, nem tudom, hogy sikerült. Egyszerűbb esetben például ha a dobozméret 4, az input 221, a mohó 22 1-et ad (az első dobozban négy, a másodikban csak egy), viszont az optimális 2 21.
7

Üres helyek minimalizálása

Rici · 2007. Júl. 21. (Szo), 20.15
Kérdés, hogy pontosan mit értesz az egyenletességen, mert ez így nem egyértelmű. Pl. valaki értheti azt, hogy a dobozonként lefoglalt egységek szórása minimális, vagy valamit hasonló.

De ha azt érted, hogy a dobozokban maradó üres helyek összegét kell minimalizálni, akkor a következő gráfalgoritmus egy lehetséges megoldás: mindegyik bemeneti elemet az irányított gráf egy pontjaként képzelünk el. Mindegyik elemről feltesszük, hogy ő egy doboz első eleme, és ekkor olyan őt követő elemekbe húzunk belőle irányított éleket, amik lehetnek a közvetlenül következő doboz első elemei. Az él súlya pedig annyi, amennyi ezen elrendezés esetén üresen marad az él kezdőpontjának dobozából. Mielőtt ezeket az éleket megcsinálnánk, fel kell venni a bemeneti lista végére egy fiktív farokelemet, ami az utolsó utáni fiktív doboz első elemét szimbolizálja. Ha megvannak az élek, akkor egyszerűen meg kell keresni a legrövidebb utat az első elemtől a fiktív utolsó elemig. A legrövidebb út pontjai jelölik a dobozok első elemét.