Polnjenje košev

Iz MaFiRaWiki

PROBLEM:
Imamo n elementov z utežmi w1,w2,...,wn, ki jih moramo razporediti v koše kapacitete M. Pri tem želimo uporabiti čim manj košev.

HEVRISTIČNE STRATEGIJE ZA POLNJENJE KOŠEV:

NIFF (nonincreasing first fit):
Vse elemente najprej razporedimo po nenaraščajočem vrstnem redu. Potem vsakega postavimo v prvi koš,
v katerem je še dovolj prostora zanj.
FF (first fit):
Elementov na začetku ne sortiramo, ampak jih jemljemo po vrsti. 
Zopet damo tekoči element v prvi koš, v katerem je še prostor zanj.
BF (best fit):
Elementov na začetku ne sortiramo. Tekoči element postavimo v tisti koš,
katerega ta element najbolj zapolni (v njem ostane najmanj prostora).
NBF (nonincreasing best fit):
Elemente najprej sortiramo po nenaraščajočem vrstnem redu. Nato tekoči element postavimo v tisti koš,
katerega le ta najbolj zapolni.
NF (next fit):
Predmete jemljemo po vrsti brez predhodnega urejanja. V koš, ki je na vrsti, dajemo predmete, dokler gredo. 
Ko pridemo do predmeta, ki vanj ne gre več, vzamemo naslednji koš. 
Prejšnjih košev ne dopolnjujemo. Takemu postopku pravimo tudi "on line". 
Nobeden od teh postopkov ni optimalen.
Za postopek NIFF pa velja: 2[NIFF(I)-Opt(I)] \leq Opt(I) , če je Opt(I) optimalno število košev.
Primeri uporabe v vsakdanjem življenju:

 * polnjenje tovornjakov, vagonov, ...
 * v tekstilni industriji: kako razrezati blago, da iz njega dobiš največ kosov oblačil.
 * v lesni industriji: kako razrezati kose lesa, da iz njih dobiš največ pohištva.

Osebna orodja