Optimální algoritmus výpočtu

[jaromír]

1. příklad:

B:[[50,17],[10,19],[5,18],[1,20]];

funkce:

f(_n,_B):=block([A,B,L,i,j,k,c:0,m:0,n:_n],B:reverse(sort(_B)),A:copylist(B),L:length(B),
for i:1 thru L do (
if ( n > B[1] ) then (
A[1]:floor(n/B[1]),
m:m+A[1]*B[1],
n:n-A[1]*B[1],
A[2]:A[1]*B[1]*B[2],
c:c+A[2]
) else (
A[1]:0,A[2]:0
),
print("Pocet:",A[1],"x",B[1]," po ",B[2],"Kč =",A[2])
),
print("Celkem kusů:",m," za celkem ",c, "Kč")

);

Výpočet:
f(78,B);

Pocet: 1 x 50  po  17 Kč = 850
Pocet: 2 x 10  po  19 Kč = 380
Pocet: 1 x 5  po  18 Kč = 90
Pocet: 3 x 1  po  20 Kč = 60
Celkem kusů: 78  za celkem  1380 Kč

Druhý příklad:

B:[[1,12],[5,8],[2,8.5]];

Opět funguje.

(Programovací jazyk Maxima, funkce jdou volat i ze skriptů)

[Reklama]

[Logik]

Nefunguje - viz protipříklady v mojim postu #56 (uvádím tam vždy cenu balení, když si to budeš chtít zkusit).

[jaromír]

B:[[5,50],[3,31]];
f(9,B);

Pocet: 1 x 5  po  50 Kč = 250
Pocet: 1 x 3  po  31 Kč = 93
Celkem kusů: 8  za celkem  343 Kč

Tak tady to nejde (z důvodu že nejmenší položka má 3 kusy).
Myslím, že bych to zvládnul upravit tak, aby to vyšlo i s méně příznivými kombinacemi.
Pak to sem šoupnu.

[Logik]

:-) Nejde to proto, že je ten algoritmus blbě :-).
Vždyť
a) legální kombinace existuje
b) když doplníš 1 kus za 10.000, - , tak Ti to vybere 5+3+1, což bude poněkud předražená kombinace.
Smiřte se s tím, že problém baťohu je NP úplnej a jde vyřešit pseudopolynomiálně
dynamickým programováním, nic lepšího vymyslet nejde...

PS: Základní problém je v tom, že v ideální kombinai nemusí bejt zastoupený balení s nejlepším poměrem ceny, a naopak tam může bejt zastoupenej výrobek s nejhorším poměrem cena/výkon.... - takže jakékoli heuristiky selhávají a je třeba prohledat celý stavový prostor.

[jaromír]

Jo s tím jedním kusem za 10000 tisíc to mě nenapadlo. Myslel jsem spíš že vysloveně nevýhodné balíčky by se rovnou vyloučily. Jenže to by musel udělat ten program.

[Reklama]

[Logik]

Jenže jak zjistíš, který jsou vysloveně nevýhodný? Ten balíček nemusí stát 10000, stačí by byl za 13Kč a je to horší. Naopak za 11Kč je to nejlepší kombinace... To zjistit nejde, aniž bys to spočítal...

[jaromír]

fr(_n,_c,_A,_k):=block([n:_n, c:_c, A:copylist(_A), i, j, x, ni, ci, imin, k:_k],
if k > 0 then (j:floor(n/A[k][1]),if j>0 then (
for i:0 thru j do (ni:n-i*A[k][1],ci:c+i*A[k][2],A[k][3]:i,fr(ni,ci,A,k-1))
) else (fr(n,c,A,k-1))) else (if (n=0) then (if z=0 then (AB:copylist(A),z:c)
  elseif (z>c) then (z:c,AB:copylist(A)))),[z,AB])$

f(_n,_B):=block([n:_n,A,AB,AA,c:0,L,z:0,s],AA:(sort(_B)),L:length(AA),A:[],
for i:1 thru L do (A:append(A,[flatten([AA,0])])),AB:copylist(A),s:fr(n,c,A,L),print(s))$

B:[[5,50],[3,31]];
f(11,B)$
[112,[[3,31,2],[5,50,1]]]

Celková cena 112Kč (1x po 5 ks á 50Kč, 2x po 3 ks á 31 Kč)

B:[[1,100],[2,8],[5,5]];
f(23,B);
[47,[[1,100,0],[2,8,4],[5,5,3]]]

Celková cena 47Kč
(žádný balíček:  1ks á 100Kč)
(4 balíčky po 2 ks á 8Kč)
(3 balíčky po 5 ks á 5Kč)

prochází možnosti od největších, ty které překročí limit zahazuje a nepočítá dál. Limit se snižuje.
Výpočet pro větší hodnoty je pomalý.

[Logik]

Promiň, na todle se nedá reagovat. Chaotickej kód bez jedinýho komentáře s jednompísmenejma proměnejma u kterejch není jasný co vlastně znamenaj, navíc bez jakýhokoli rozumnýho formátování.

Nerozumím, co si tím chtěl říct, ale je to jasnej příklad, jak se programovat NEMÁ.

[jaromír]

Tak jsem to zjednodušil, sice to trvá déle, ale je to přehlednější:

Kód: [Vybrat]

funkce_rekurzivni(Pocet_polozek,Celkem_Kc,Pole_D,Polozka):=block(
[   i,
    Pocet,
    Pole_A: copylist(Pole_D)],

if Polozka > 0 then (
    Pocet: floor(Pocet_polozek/Pole_B[Polozka][1]),
    if Pocet > 0 then (
        for i:0 thru Pocet do (           
            Pole_A[Polozka]: i,
            funkce_rekurzivni(Pocet_polozek-i*Pole_B[Polozka][1],Celkem_Kc+i*Pole_B[Polozka][2],Pole_A,Polozka-1)
        )
    )
    else (
        funkce_rekurzivni(Pocet_polozek,Celkem_Kc,Pole_A,Polozka-1)
    )
)
else (
    if (Pocet_polozek=0) then (
        if ((Suma=0) or (Suma > Celkem_Kc)) then (
            Suma: Celkem_Kc,
            Pole_C: copylist(Pole_A)
        )
    )
),[Suma,Pole_C])$

optimum(Pocet_polozek,Pole_Balicku):=block(
[   Pole_A,
    Pole_B,
    Pole_C,
    Celkem_Kc: 0,
    Polozka,
    Suma: 0,
    Vysledek],

Pole_B: sort(Pole_Balicku),
Polozka: length(Pole_B),
Pole_A: makelist(0,Polozka),
Pole_C: copylist(Pole_A),

Vysledek: funkce_rekurzivni(Pocet_polozek,Celkem_Kc,Pole_A,Polozka),
[Vysledek,Pole_B]
)$
Zadám pole obsahující jednotlivé balíčky (1ks á 9Kč, 2 ks á 8Kč ...atd.):
Zavolám funkci obsahující právě toto pole a požadovaný počet položek:

Kód: [Vybrat]

B:[[1,9],[2,8],[5,5]]$
optimum(23,B);
Funkce vrátí vypočítanou celkovou cenu a seznam počtů jednotlivých balíčků.

[Logik]

A čím se to liší od předchozího algoritmu?

[jaromír]

Projde to všechny možnosti.

[Logik]

Jo, už jsem to pochopil. Fuj. Víc se k tomu říct nedá. Pročti si diskusi a najdeš tam několikrát zmiňovaný daleko rychlejší řešení. Heslo "dynamický programování".

[Ghost]

Dynamicke programovani je reseni, ale rekl bych, ze narocnejsi na pochopeni.

Mozny nastrel reseni, ktery by mel byt po malych upravach funkcni a optimalni.
Kosik si predstav treba jako list, nebo multiset.
Jednotlive velikosti baleni si ocisluj od jednicky treba.
Je to oklestena metoda B&B - orezevam jen stavy, ktere nikam nevedou.

Kód: [Vybrat]

1. vytvor trivialni konfiguraci - tj. v Tvem pripade prazdny kosik
2. oznac toto trivialni reseni jako dosud nejlepsi
3. vloz jej na zasobnik
4. pokracuj dokud neni zasobnik prazdny a delej nasledujici kroky:
1. generuj nove konfigurace
Tady je dulezite se neopakovat -> tj. nevytvaret si uz jednou vytvorene kosiky.
Ukladat si je do nejake mapy pod hashem a kontrolovat jestli uz jsi je nemel je blbost - pametova narocnost.
Reseni, ktere ti bude generovat unikatni neusporadane konfigurace by mohlo byt takoveto:
(Pozn. na zasobniku se bude generovat silne nevyvazeny strom nakloneny na jednu stranu - zalezi jak zacnes, ze je nevyvazeny nicemu nevadi :))
Dulezite je to ocislovani baleni! Ze stavu, ktery je na vrcholu zasobniku vygeneruj nove stavy tak, ze pridej
nove baleni - ale pridej vzdy jen ty, ktere maji CisloBaleni >= nez posledne vlozene baleni!
2. over u nove konfigurace jestli se jedna stale o platne reseni
3. pokud je neplatne tak stav vyjmy ze zasobniku a pokracuj
4. jestli je reseni tak over jestli se nejedna o lepsi reseni, nez je posledne nalezene. Jestli jo, tak jej oznac jako nejlepsi.
5. pokracuj
5. pokud je po vsech techto krocich nejlepsi reseni porad to trivialni tak reseni neexisuje


Ted jen kratka "vizualizace".
Mam tri baleni, ktere si ocisluju 1,2,3 - je jedno jakou maji cenu, jen popis jak se generuje.
Jednotlive kroky:
1. empty - tj. prazdny kosik
2. bytvorim stavy a na zasobniku mam ted {1}, {2}, {3} - predpokladejme, ze jsou vsechna resenim (poradi nezalezi, muze byt i naopak)
3. na vrcholu mam ted teda {1}, takze si jej vytahnu a stejnym postupem generuju dalsi stavy a dostanu {1,1}, {2,1}, {3,1}
4. stav {2} se expanduje uz jen na {2,2} a {3,2}
5. stav {3} se expanduje uz jen do {3,3}, tady jde videt to nakloneni doleva


[Ghost]

sakra, omluvte ty pravopisne chyby ..
zapomnel jsem dopsat:
2. over u nove konfigurace jestli se jedna stale o platne resenim jestli jo, tak zase vloz na zasobnik

[Logik]

Já nevim, imho to neni o nic jednodušší než dynamické programování. Prostě se mi to zdá jako snaha vymejšlet kolo....