LINUX-BG   Adres : http://www.linux-bg.org
Vuvedenie v dinamichnata optimizatsiia
Ot: vesso
Publikuvana na: 30-08-2005
Adres na statiiata: http://www.linux-bg.org/cgi-bin/y/index.pl?page=article&id=devs&key=374961042
Vuvedenie v dinamichnata optimizatsiia

Zadacha: Imame opredelen broi moneti ot razlichni denominatsii. Imame i suma koiato triabva da platim. Da se napishe funktsiia koiato da izchisli minimalniia broi moneti neobhodimi za plashtane na sumata. Ako ne mozhem da formirame sumata s nalichnite moneti funktsiiata triabva da vurne chislo po-goliamo ot broia na monetite kato indikatsiia za greshka.

Purvi opit: Oslaniame se na instinktite si. Znaem che kolkoto poveche edri moneti polzvame tolkova po-maluk broi moneti shte sa neobhodimi. Zatova vzimame nai-goliamata moneta (koiato vse pak e po-malka ot sumata), namaliavame sumata sus stoinostta na monetata i izvikvame sushtata funktsiia s namalena suma no i s edna moneta po-malko. Kogato sumata stigne do nula vrushtame 0 moneti. Kogato broia moneti stigne do 0 vrushtame 1 (greshka). Na piton funktsiiata izglezhda taka:

def coins1(purse, amount):
     if amount == 0:
         return 0
     if amount < 0 or len(purse) == 0:
         return len(purse) + 1
     purse.sort()
     for index in range(len(purse) - 1, -1, -1):
         if purse[index] <= amount:
             new_purse = purse[:index] + purse[index+1:]
             new_amount = amount - purse[index]
             return 1 + coins1(new_purse, new_amount)
     return len(purse) + 1

Testvame naburzo:

print coins1([50], 20), ' -> >1'
print coins1([50], 50), ' -> 1'
print coins1([10, 20, 50], 20), ' -> 1'
print coins1([5, 5, 10, 10, 10, 20, 50], 25), ' -> 2'
print coins1([5, 5, 10, 10, 10, 50], 25), ' -> 3'
print coins1([5, 5, 10, 20, 20, 20, 50, 50], 60), ' -> 2'

Neshtata izglezhdat dobre ... dokato ne probvame:

print coins1([2, 2, 2, 5], 6), ' -> 3'

Ochakvame rezultat 3 (3 moneti po 2 st) no funktsiiata vrushta 5, t.e. ne mozhe da napravi sumata ot zadadenite moneti. A ne mozhe zashtoto vednuzh reshila da polzva monetata ot 5 st niama kak da napravi ostatuka ot 1 st.

Tozi algoritum mozhe da se uslozhni taka che ako ne mozhe da napravi new_amount da opita s po-malka moneta - togava vinagi shte uspiava i izvikvaneto coins1([2, 2, 2, 5], 6) shte vrushta korektna stoinost. Obache izvikvane coins1([1, 1, 1, 1, 1, 1, 5, 20, 20, 20, 50], 60) shte vrushta 7 (50 + 5 + 1 + 1 + 1 + 1 + 1) vmesto korektnoto 3 (20 + 20 + 20).

Opisaniiat algoritum v opit 1 e alchen (greedy) zashtoto vinagi zapochva ot nai-goliamoto kandidat-reshenie. Tezi algoritmi sa lesni za pisane i rabotiat burzo no ne vinagi rabotiat korektno.


Vtori opit: Qvno nastoiavaneto da polzvame nai-goliamata moneta ne vinagi e udachno. Zatova za vsiaka moneta shte opitame kakvo shte stane (1) ako monetata uchastva i (2) ako monetata ne uchastva v sumata. Sled tova shte vzemem po-dobroto reshenie. Otnovo se oformia rekursivna funktsiia:

def coins2(purse, amount):
     if amount == 0:
         return 0
     if amount < 0 or len(purse) == 0:
         return len(purse) + 1
     without = coins2(purse[1:], amount)
     if without >= len(purse):
         without = len(purse) + 1
     with = coins2(purse[1:], amount - purse[0])
     if with >= len(purse):
         with = len(purse) + 1
     return min([without, with + 1])

Puskame gornite testove i vsichko vurvi dobre, vklyuchitelno i tezi primeri koito zatrudniavaha purvata funktsiia ... dokato ne opitame:
print coins2([1, 1, 1, 1, 1, 1, 2, 2, 5, 5, 5, 10, 10, 10 ,10, 20, 20, 20, 20, 50, 50, 50], 275), ' -> 12'

Funktsiiata raboti viarno no nepriemlivo dulgo vreme. Prichinata e che ako ima 1 moneta funktsiiata che obraboti 2 sluchaia (2^1) - ediniia sus a drugiia bez monetata. Ako ima 2 moneti funktsiiata shte obraboti 4 sluchaia (2^2) i suotvetno ako ima N moneti funktsiiata shte triabva da obraboti 2^N sluchaia. Ili zapisano v t.nar. O notatsiia slozhnostta na funktsiiata e O(2^N). Takava funktsiia, dori napisana na asembler, shte raboti godini nared da smetne suma ot stotina moneti.


Treti opit: reshenie s dinamichna optimizatsiia.

Imeto na poniatieto "dinamichna optimizatsiia" idva ot povedenieto na programite koito dinamichno izgrazhdat tablitsi s mezhdinni rezultati. Polzvaiki tezi mezhdinni rezultati lesno i burzo se stiga do krainiia rezultat. Eto i funktsiiata:

def coins3(purse, amount):
     big = len(purse) + 1
     current_row = [0]
     for amount_idx in range(amount):
         current_row.append(big)
     all_rows = [current_row]
     for coin in purse:
         prev_row = current_row
         current_row = []
         for amount_idx in range(amount + 1):
             if amount_idx < coin:
                 current_row.append(prev_row[amount_idx])
             else:
                 without = prev_row[amount_idx]
                 with = 1 + prev_row[amount_idx - coin]
                 current_row.append(min([with, without]))
         all_rows.append(current_row)
     return current_row[amount]

Obiasnenie:
Neka izvikame funktsiiata s coins3([2, 2, 2, 2, 5, 5, 10], 11). Funktsiiata si izbira proizvolen kod za "nevuzmozhna kombinatsiia", po-goliam ot broia na monetite. Sled tova si suzdava edin spisuk (ednomeren masiv) sus slednoto sudurzhanie:

[0, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8]

Spisukut ima tolkova elementa kolkoto e sumata koiato ni triabva (11) plyus edno (za suma 0). Smisulut na taka polucheniiat red e che s nikakvi moneti (zashtoto oshte nikakvi moneti ne sa obraboteni) mozhem da postignem suma 0 sus 0 moneti (purviia element) i ne mozhem da napravim nikakvi drugi sumi (8 = kod za nevalidna suma). Indeksut v tozi spisuk e sumata koiato iskame da napravim, a stoinostite - broia moneti neobhodimi za postiganeto na sumata.

Sled tova za vsiaka moneta si suzdavame nov spisuk, v koito:
- Ako indeksut (sumata) e po-maluk ot monetata prosto kopirame stoinostite ot predishniia red.
- v protiven sluchai sravniavame broia moneti ot sushtiia indeks na predishniia red (t.e. broia moneti bez tekushtata) s edno plyus broia moneti ot predishniia red, neobhodim za postigane na suma namalena sus stoinostta na tekushtata moneta. Dobaviame po-malkata ot tezi stoinosti kum tekushtiia red.

Sled obrabotvane na purvata moneta (2 st) spisukut izglezhda taka:

[0, 8, 1, 8, 8, 8, 8, 8, 8, 8, 8, 8],

Smisulut na tova e che s 0 moneti mozhem da postignem suma 0, s 1 moneta mozhem da postignem suma 2 (indeks 2) a ostanalite sumi ne mogat da budat napraveni s 1 moneta ot 2 st.

Kogato programata zavurshi spisukut all_rows sudurzha slednoto:

[
[0, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8],
[0, 8, 1, 8, 8, 8, 8, 8, 8, 8, 8, 8],
[0, 8, 1, 8, 2, 8, 8, 8, 8, 8, 8, 8],
[0, 8, 1, 8, 2, 8, 3, 8, 8, 8, 8, 8],
[0, 8, 1, 8, 2, 8, 3, 8, 4, 8, 8, 8],
[0, 8, 1, 8, 2, 1, 3, 2, 4, 3, 8, 4],
[0, 8, 1, 8, 2, 1, 3, 2, 4, 3, 2, 4],
[0, 8, 1, 8, 2, 1, 3, 2, 4, 3, 1, 4]]

Posledniiat red sudurzha broia moneti neobhodimi za suma ravna na indeksa v reda. Mozhem da postignem:
- s 0 moneti: suma 0
- s 1 moneta: suma 2, 5 i 10 st (s takiva moneti razpolagame)
- s 2 moneti: sumi 4 i 7 st.
- s 3 moneti: sumi 6 i 9 st.
- s 4 moneti: sumi 8 i 11 st.
- ne mozhem da napravim sumi 1 i 3 st.

Otgovorut na nashata zadacha e v posledniia red, poslednata kolona.
Paradoks e che namerihme resheniiata na vsichki sumi po-malki ot tursenata, pri tova - pone v niakoi sluchai - po-efektivno otkolkoto namiraneto samo na edno reshenie ot vtoriia ni opit.

Po-vnimatelnite mozhe bi sa zabeliazali che kum spisukut all_rows samo se dobavia no ot nego ne se chete. Programata mozhe da raboti chudesno i bez nego. Takuv spisuk e neobhodim kogato iskame da vidim koi moneti uchastvat v reshenieto. Praviloto e:
1. Trugvame ot dolniia desen ugul i ot poslednata moneta
2. Sravniavame chisloto nad tekushtoto:
2.1. Ako e sushtoto znachi tekushtata moneta ne uchastva v rezultata. Zapazvame sushtiia indeks.
2.2. Ako e razlichno znachi tekushtata moneta uchastva v rezultata. Namaliavame indeksa sus stoinostta na tekushtata moneta.
3. Minavame na po-gorniia red i na predishnata moneta.
4. Ako sme stignali do 0 sme gotovi, v protiven sluchai otivame na t. 2.


Zadachi za uprazhnenie:

1. Prepravete funktsiiata coins3 taka che da izpolzva samo edin spisuk (ednomeren masiv)

2. Pesho ima da dava na Gosho dadena suma. Znaem kakvi moneti imat i Pesho i Gosho. Da se napishe programa koiato da izchisli minimalniia broi moneti smeniavashti sobstvenika si taka che Pesho da se izdulzhi. Znaem che e dopustimo Gosho da vrushta resto. Funktsiia:

def exer2(pesho_coins, gosho_coins, amount):

Izvikvane:

print exer2([10, 10, 20, 50], [5, 10, 20], 40)

rezultat: 2 - Pesho dava edna moneta ot 50 i poluchava resto edna moneta ot 10

3. Mozhem da nosim maksimum X kg. Ima N predmeta s teglo Gi kg i stoinost Vi. Kakva e maksimalnata stoinost na predmetite koito mozhem da vzemem. Funktsiia:

def exer3(MaxWeight, Weights, Values):

Izvikvane:

print exer3(50, [24, 25, 45], [5, 6, 10])

rezultat: 11 - purviia i vtoriia predmet

(Podskazka: Google "knapsack problem")


24 Avgust 2005
Veselin Kostadinov

Redaktsiia ot 31 Avgust 2005: Vmesto termina "dinamichna optimizatsiia" statiiata polzvashe "dinamichno programirane" (bukvalen prevod ot angliiskiia termin "dynamic programming"). Blagodaria na d.vasilev.

<< Kraina tsel: FreeBSD | Programirane pod Linuks. Vuvedenie za nachinaeshti. >>

Avtorite na saita, kakto i tehnite sutrudnitsi zapazvat avtorskite prava vurhu sobstvenite si materiali publikuvani tuk, no te sa copyleft t.e. mogat svobodno da budat kopirani i razprostraniavani s iziskvaneto izrichno da se upomenava imeto na avtora, kakto i da se publikuva na vidno miasto, che te sa vzeti ot originalniia im URL-adres na tozi survur (http://www.linux-bg.org). Avtorskite prava na prevodnite materiali prinadlezhat na tehnite avtori. Ako s publikuvaneto tuk na niakakuv material nevolno sa narusheni nechii prava - sled konstatiraneto na tozi fakt materialut shte bude svalen.

All trademarks, logos and copyrights mentioned on this site are the property of their respective owners.
Linux is copyright by Linus Torvalds.
© Linuks za bulgari EOOD 2007
© Slavei Karadjov 1999 - 2006

All rights reserved.

Изпълнението отне: 0 wallclock secs ( 0.18 usr + 0.01 sys = 0.19 CPU)