Az optimális választás feladata
Egy hátizsákba meghatározott térfogatú és fontossági értékű tárgyakat kel el beraknunk úgy, hogy az összes pontérték minél nagyobb legyen. Az összes tárgy térfogata együtt nagyobb, mint a hátizsák térfogata, tehát az összes tárgy nem rakható be. Meg kell határozni, hogy a tárgyak mely kombinációja esetén lesz a pontérték maximális.
Heurisztikus próbálkozás: - Csökkenő pontérték szerint tesszük be a tárgyakat
- Relatív fontosság (pontérték/térfogat) szerint csökkenő sorrendben töltjük fel a hátizsákot
A megoldást nem fogadjuk el, ha a feladat mérete a kitevőben van. Ha az alap a feladat mérete, akkor jó megoldásnak tekintjük (nk).
Általános feladat
Adott tárgyak halmazából valamilyen optimalitási szempont alapján a legjobb részhalmaz kiválasztása. Módszer: - előállítjuk az összes lehetséges részhalmazát a halmaznak
- Kiszámoljuk a pontértéket
- Kiszámoljuk a térfogat-értéket, hogy még beleférjen
- Kiválasztjuk a maximális pontértékűt
Ez egy Branch-Bound algoritmus, amely szeleteket vesz a keresési térben; az eleve reménytelen ágakkal nem próbálkozik.
A hátizsákos feladatra: Ha kivesszük az utoljára berakottat, a hátralévő összes lehetséges elem berakásával kaphatunk-e jobb megoldást, mint az eddigi legjobb? Ez a vágás. Ha ezt nem teljesíti, nem próbálkozunk ezzel az ággal.
Algoritmus
Procedure probal(i: integer, TW, AV: integer)
Var AV1: integer;
Begin
If TW+A[i].W<=limW then begin
S:=S+[i];
If i<n then probal(i+1, TW+A[i].W, AV)
Else
If AV>MAXV then begin
MAXV:=AV;
OPTS:= S;
End;
S:=S-[i];
End;
AV1:= AV-A[i].V;
If AV1>MAXV then begin
If i<n then probal(i+1, TW, AV1)
Else
begin
MAXV:=AV1; {maximum kiválasztás}
OPTS:=S;
End;
End;
End;
Magyarázat
I: a szinteket tárolja (hányadik tárggyal próbálkozunk)
TW: a hátizsákban lévő tárgyak összes súlyértéke
AV: híváskor az összes tárgy pontértékéttartalmazza
LimW: a hátizsákba rakható tárgyak maximális összsúlya
If TW+A[i].W: ha még a súlykorláton belül vagyunk, a következő tárgyat is betehetjük
S:=S+[i]: betesszük a következő tárgyat
If i<n: ha van még további tárgy, akkor nincs kész. Újrahívjuk a megnövelt súlyértékkel (az aktuális tárgyat beraktuk – TW+A[i].W)
Else if AV>MAXV: megtelt a hátizsák. Nagyobb-e a berakott új tárggyal a térfogat,befér-e? AV1:= AV-A[i].V: az utoljára berakott tárgy nélkül kaphatunk-e jobb megoldást, mint az eddigi legjobb?
If i<n: ha van még tárgy, be tudjuk rakni? (probal)
MAXV: feljegyezzük, mennyi a hátizsákban lévő pontérték
OPTS: optimális halmaz, a felhasznált tárgyak indexei
Ha az utolsó probal eljárás hívódik meg, a következő else ág nem hajtódik végre.
Hívása: probal(1,0,totv): probal(első elem, üres táska, tárgyak fontossági sorrendjeinek összege)
Az A tömbbe a tárgyakat súly szerinti növekvő sorrendben kell berakni
