knapsack.pdf

Jarosław Henke I rok NSI na podstawie M.Sysło ALGORYTMY

Problem plecakowy (KNAPSACK PROBLEM) .

Zagadnienie optymalizacji zwane problemem „plecakowym” sw Ģ nazw ħ wzi ħ ło z analogii do

sytuacji praktycznej podobnej do problemu pakowania plecaka. Chodzi o to, by zapakowa ę

maksymalnie cenny zbiór przedmiotów nie przekraczaj Ģ c ładowno Ļ ci (no Ļ no Ļ ci lub

pojemno Ļ ci) baga Ň u. Mo Ň na tu wyró Ň ni ę kilka sposobów rozumowania. Opis rozpoczynamy

od zagadnienia najbardziej ogólnego.

Ogólny problem plecakowy

Dane:

• Przedmioty które oprócz unikatowej nazwy P i posiadaj Ģ dwie cechy:

1. mas ħ m i lub je Ļ li kto woli obj ħ to Ļę (bo pakowanie plecaka mo Ň emy

optymalizowa ę ze wzgl ħ du na mas ħ (ci ħŇ ar) lub ze wzgl ħ du na obj ħ to Ļę

2. cen ħ c i .

Wyniki:

• ilo Ļ ci k i poszczególnych przedmiotów (mog Ģ by ę zerami)

Formuła problemu:

• Niech:

o W jest warto Ļ ci Ģ wszystkich przedmiotów spakowanych w plecaku.

o M max jest maksymaln Ģ mas Ģ (obj ħ to Ļ ci Ģ ) plecaka

• Znale Ņę warto Ļ ci k i , takie aby:

było mo Ň liwie najwi ħ ksze, oraz

ii.

≥

iii.

≥ 0

Rozwi Ģ zaniami dopuszczalnymi nazywa ę b ħ dziemy wszystkie zbiory ilo Ļ ci k i spełniaj Ģ ce

warunek ii.

Rozwi Ģ zaniem optymalnym b ħ dzie ten zbiór ilo Ļ ci k i , który spełni warunek i.

i - nazwiemy funkcj Ģ optymalizacji

ii oraz iii - nazwiemy ograniczeniami lub warunkami brzegowymi .

Zagadnienie w swej prostocie sformułowania wydawa ę by si ħ mogło łatwym do rozwi Ģ zania

problemem. Nic bardziej mylnego. Wbrew pozorom problem plecakowy wygenerował wiele

do Ļę skomplikowanych algorytmów rozwi Ģ zuj Ģ cych go.

Strona 1

Jarosław Henke I rok NSI na podstawie M.Sysło ALGORYTMY

Algorytm zachłanny dla ogólnego zagadnienia plecakowego.

Działanie zachłanne przypomina naturalne podej Ļ cie człowieka do zagadnienia pakowania

plecaka. Pakuj Ģ c plecak tak aby pomie Ļ ci ę w nim jak najwi ħ ksz Ģ warto Ļę człowiek

kierowałby si ħ - jednym z lub w sposób mieszany - nast ħ puj Ģ cymi kryteriami:

1) Starałby si ħ wybiera ę rzeczy najcenniejsze w kolejno Ļ ci od najdro Ň szej do najta ı szej.

≥ ≥ ≥ ⋯ ≥

2) Starałby si ħ zabiera ę rzeczy jak najmniejsze poczynaj Ģ c od najl Ň ejszego przedmiotu,

na najci ħŇ szym sko ı czywszy.

≤ ≤ ≤ ⋯ ≤

3) Starałby si ħ wybiera ę przedmioty w kolejno Ļ ci ustawionej nierosn Ģ co ze wzgl ħ du na

iloraz ceny do wagi przedmiotu. Taki iloraz stanowi bowiem jednostkow Ģ warto Ļę

przedmiotu (warto Ļę przypadaj Ģ c Ģ na jednostk ħ masy lub obj ħ to Ļ ci).

≥

≥ ⋯ ≥

Człowiek działaj Ģ c strategicznie i po kolei, podejmuje decyzje optymalne z punktu widzenia

danego kroku. Tak wi ħ c w pierwszym kroku wg planu nr 1 wzi Ģ łby rzecz najdro Ň sz Ģ , wg

planu nr 2 wzi Ģ łby du Ň o lekkich, za Ļ wg strategii nr 3 wyst ħ puje ju Ň element wywa Ň enia cho ę

tym razem wzi Ģ łby maksymalna ilo Ļę przedmiotów o najwi ħ kszej warto Ļ ci jednostkowej.

Wła Ļ nie takie działanie nazywamy działaniem zachłannym .

Zbadajmy teraz do jakich rezultatów doprowadzi nas post ħ powanie według ka Ň dej z trzech

strategii zachłannych podczas pakowania 6 przedmiotów do plecaka o no Ļ no Ļ ci M max =10 jm 1 ,

przy czym ka Ň dego przedmiotu mamy dowoln Ģ ilo Ļę k i .

Dane:

P i

c i [zł] m i [jm]

1 Koszula flanelowa

2 Spodnie d Ň insowe

150

3 Sweter

250

4 Czapka baseballowa

5 K Ģ pielówki

6 Obuwie sportowe

100

Tabela 1. Dane do ana lizy ro zwią zań proble mu plecakowego.

Ad.1

1 jm – jednostka miary – umowna jednostka miary dla potrzeb przykładu.

Strona 2

Jarosław Henke I rok NSI na podstawie M.Sysło ALGORYTMY

Zaczynamy od wybrania rzeczy najdro Ň szej. Jest ni Ģ sweter, czyli przedmiot o indeksie 3.

Sweter wa Ň y 6 jm, a wi ħ c mo Ň emy zapakowa ę ich co najwy Ň ej 1 szt. Zatem k 3 =1.

Wypełniony swetrami plecak wa Ň y 6 jm, musimy zatem jeszcze doładowa ę 4 jm. Najdro Ň szy

przedmiot nie przekraczaj Ģ cy tej wagi to czapka baseballowa o indeksie 4. Do plecaka

zmie Ļ ci si ħ dokładnie jedna k 4 =1 szt. Plecak mamy pełen.

Nasz wynik zatem to:

k 1 =0, k 2 =0, k 3 =1, k 4 =1, k 5 =0, k 6 =0

za Ļ uzyskana warto Ļę plecaka, wynosi:

W = k 3 c 3 + k 4 c 4 = 1 * 250 zł + 1 * 35 zł = 285 zł

Ad.2

Teraz pakowa ę b ħ dziemy „du Ň o” zaczynaj Ģ c od rzeczy najl Ň ejszej. Najl Ň ejsze w naszym

zestawie s Ģ k Ģ pielówki o indeksie i =5. Masa m 5 =3 jm. W plecaku zmie Ļ cimy ich a Ň k 5 =3szt.

Plecak nie b ħ dzie wypełniony do ko ı ca, brakuje 1 jm ale nie ma towaru, który miałby co

najwy Ň ej tak Ģ mas ħ .

Warto Ļę plecaka w tym przypadku wyniesie:

W = k 5 c 5 =3 * 10 zł = 30 zł

Jak wida ę mniej ni Ň w poprzednim przypadku, a wi ħ c nie optymalnie. Wypróbujmy teraz

sposób trzeci.

Ad.3

Wyliczmy warto Ļ ci jednostkowe poszczególnych przedmiotów. W tym celu uzupełnimy

tabel ħ 1 o kolumn ħ c i /m i .

P i

c i [zł] m i [jm] c i /m i

1 Koszula flanelowa

7 10,71

2 Spodnie d Ň insowe

150

8 18,75

3 Sweter

250

6 41,67

4 Czapka baseballowa

4 8,75

5 K Ģ pielówki

3 3,33

6 Obuwie sportowe

100

9 11,11

Tabela 2. Wartośc i jedno stkowe.

Plecak zaczniemy zapełnia ę swetrami, gdy Ň one maj Ģ najwi ħ ksz Ģ warto Ļę jednostkow Ģ . Do

plecaka uda nam si ħ zapakowa ę 1 taki sweter. Da to ł Ģ czn Ģ mas ħ 6 jm. Musimy wi ħ c zapełni ę

jeszcze 4 jm. Zmieszcz Ģ si ħ jeszcze k Ģ pielówki lub czapka baseballowa. Wybieramy czapk ħ

Strona 3

Jarosław Henke I rok NSI na podstawie M.Sysło ALGORYTMY

baseballow Ģ (4 jm) gdy Ň jej warto Ļę jednostkowa jest wy Ň sza od warto Ļ ci jednostkowej

k Ģ pielówek. Sprawd Ņ my jak Ģ uzyskali Ļ my warto Ļę plecaka?

W = k 3 c 3 + k 4 c 4 =1 * 250zł + 1 * 35zł = 285 zł

Tym sposobem otrzymali Ļ my warto Ļę tak Ģ sam Ģ jak w metodzie 1, Ale ta metoda wydaje si ħ

najbardziej logiczna. Nale Ň y uzna ę , ze metoda optymalizacji poprzez porz Ģ dkowanie wg.

warto Ļ ci jednostkowej przynosi najlepszy rezultat. Czy jednak jest to warto Ļę optymalna? W

naszym przykładzie tak ale mo Ň na wykaza ę , Ň e nie zawsze ten sposób rozumowania prowadzi

do wyniku optymalnego 2 . Wyniki metod 1 i 2 nie s Ģ optymalne za Ļ działaj Ģ c wg metody 3

cz ħ sto otrzymujemy wynik przybli Ň ony. Mimo to metoda nr 3 wydaje si ħ jedyn Ģ spo Ļ ród

rozwa Ň anych, godn Ģ uwzgl ħ dnienia w metodach zachłannych rozwi Ģ zuj Ģ cych problem

plecakowy.

GREEDY-GENERAL-KNAPSACK

Dane:

, , = 1,2,…,;

gdzie P i – przedmiot, m i – masa i-tego przedmiotu, c i – cena i-tego przedmiotu

UporzĢdkowane tak, aby:

≥

≥ ⋯ ≥

M max – noĻnoĻę (pojemnoĻę) plecaka.

Wyniki:

, ,…, takie, Ňe

≥ 0

oraz

≥

1) Dla kolejnych przedmiotów , = 1,2,3,.., wykonaj krok 2).

2) OkreĻl najwiħkszĢ wartoĻę

, spełniajĢcĢ nierównoĻę

≤

3) Znaleziona wartoĻę plecaka wynosi:

= − .

= + + …+

KONIEC

2 Patrz Maciej M. Sysło Algorytmy WSIP Warszawa 2002 s.217-218

Strona 4

Przyjmij

Jarosław Henke I rok NSI na podstawie M.Sysło ALGORYTMY

Programowanie dynamiczne dla ogólnego problemu plecakowego

Metoda programowania dynamicznego zapewnia znalezienie optymalnego rozwi Ģ zania

problemu plecakowego. Polega ona na umiej ħ tnym zastosowaniu zasady „dziel i zwyci ħŇ aj”.

Generalnie chodzi o to aby podzieli ę zagadnienie, na problemy mniejsze – łatwiejsze do

rozwi Ģ zania. Fajnie byłoby, gdyby pojemno Ļę plecaka była mała i mała była tak Ň e liczba

rodzajów przedmiotów do upakowania. No to znajd Ņ my rozwi Ģ zania dla sytuacji jak gdyby

trzeba było wypełni ę plecak tylko jednym rodzajem przedmiotów. Dodatkowo niech

pojemno Ļę maksymalna plecaka zmienia si ħ od jednostkowej, do maksymalnej co 1. Warto Ļ ci

wpisywa ę b ħ dziemy w tabeli w której numer wiersza i odpowiada ę b ħ dzie numerowi

przedmiotu z tabeli1 3 za Ļ numer kolumny j niech b ħ dzie kolejn Ģ całkowit Ģ pojemno Ļ ci Ģ

plecaka.

P ij

ccjcssc

Pierwszy wiersz wypełni ę najłatwiej albowiem mamy do dyspozycji tylko przedmiot jednego

rodzaju, którym napełniamy plecak o kolejnych (1, 2…10) pojemno Ļ ciach. W kolejne

rubryczki wpisujemy warto Ļ ci plecaka. Pierwszych sze Ļę pozycji ma warto Ļę 0 gdy Ň koszula

wa Ň y 7 jm. Dopiero od pojemno Ļ ci plecaka równej 7 mo Ň emy j Ģ do niego wpakowa ę .

P i

c i m i

P ij

1 2 3 4 5 6 7

8 9 10

koszula flanelowa

1 0 0 0 0 0 0 75 75 75 75

spodnie d Ň insowe

150

sweter

250

czapka baseballowa

k Ģ pielówki

obuwie sportowe

100

Tabela 3a. Tablica P i j wa rto ści upakowań ple caka wygenero wanych przez algorytm

programowania dyna micznego – pierws zy wiers z.

W drugim wierszu do dyspozycji mamy ju Ň dwa „ciuchy”. Niestety w naszym przykładzie ich

ł Ģ czna waga przekracza dopuszczaln Ģ ładowno Ļę plecaka. Wybieramy zatem ciuch dro Ň szy

(spodnie d Ň insowe 150 zł), który zmie Ļ ci si ħ w plecaku pocz Ģ wszy od j =8. Podobnie w

przypadku trzeciego wiersza, gdzie do dyspozycji dochodzi sweter, ale tylko on mie Ļ ci si ħ w

maksymalnym dla ka Ň dego j plecaku. Wypełnijmy zatem warto Ļ ciami wiersze 2 i 3.

3 W algorytmie programowania dynamicznego, kolejno Ļę przedmiotów nie ma znaczenia, dlatego tabela nr 1 nie

musi by ę sortowana. Przyp. aut.

Strona 5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: