ot vesso(30-08-2005)

reiting (22)   [ dobre ]  [ zle ]

Printer Friendly Variant za otpechatvane

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. >>