Optimální algoritmus výpočtu

[Waseq]

Pokud je výpočet složitý, a tady asi bude, zbývá ještě možnost si průběžná řešení ukládat. A při každém požadavku se podívat, zda tuto variantu chtěl někdo předtím. Ano -> nemusím počítat, ne -> spočítám, uložím.
Nevhodné při častých změnách cen. A určitě ohlídat žádosti o milion balení, při exponenciální složitosti by to mohlo trvat trošku dýl.

[Reklama]

[pedro]

Samozrejme vim ze tato situace v realu by nastat nemela. jen jsem zvolil takto vysoke cislo kvuli nazornosti.
Stale nechavam puvodni jednodussi algorytmus zalozeny na celociselnem deleni ktery pro 99% situaci bude optimalni. jen jsem zde chtel zjistit zda neexistuje 100% metoda ktera neni vypocetne narocna, coz asi neni.

Souhlas, taky bych nechal to, co funguje v 99% pripadu. Zivot neni rizeni jaderne elektrarny. Zadne elegantni reseni me samotneho nenapada.

[kosta]

jestli neni jednodussi dat ceny podle poctu ks, napr.
cena1 = 1-4 ks
cena2 = 5-9ks
cena3 = 10ks a vic
nemusis nic pocitat

[mt]

Škoda nevyužít práce generací studentů FELu, kteří se problémem batohu zabývali v předmětu 36PAA ;-) Nějaké info třeba zde:

http://tumic.wz.cz/fel/online/36PAA/3/

[Honza S.]

Autor příspěvku má pravdu, řešení optimální sestavy balíčků je podobné problému batohu. Jednoduchý algoritmus s několika do sebe vnořenými for-cykly zvládne takovou úlohu vyřešit jen pro malý počet velikostí balíčků a kusů zboží. Uznávám že to může v praxi stačit ale řešení inspirované problémem batohu a dynamickým programováním bude pro větší vstupy výrazně rychlejší:

Kód: [Vybrat]

/*
   (c) Jan Stoklasa 2010 (http://www.lisp.cz)
   Reseni ulohy nejlevnejsi sestavy balicku daneho zbozi s pouzitim upraveneho problemu batohu.
   Na vstupu je počet kusů které chce zákazník koupit, počet balíčků a pak dvojice počet kusů v balíčku-cena, například vstup

   5
   2
   1 3
   2 2

   znamená že zákazník chce koupit 5 kusů zboží a na vstupu jsou 2 balíčky - balíček obsahující 1 kus s jednotkovou cenou tři a balíček
   obsahující 2 kusy s jednotkovou cenou 2.
   Program vytiskne nejlevnější dosažitelnou cenu, mohl by tisknout i sestavu balíčků ale to už nechávám za domácí úkol ;-)
*/   
 
#include <limits.h>
#include <iostream>
#include <algorithm>

using namespace std;

struct balicek
{
  int pocet_kusu;
  int cena_za_kus;
};

bool cmp(const struct balicek& a, const struct balicek& b)
{
  if(a.pocet_kusu == b.pocet_kusu)
    return a.cena_za_kus < b.cena_za_kus;
  else
    return a.pocet_kusu < b.pocet_kusu;
}

int main(void)
{
  int N;
  int POCET_KUSU;

  cin >> POCET_KUSU >> N;
  struct balicek* a = new struct balicek[N]; 
  int* m = new int[POCET_KUSU+1];

  for(int i=0;i<N;i++)
    cin >> a[i].pocet_kusu >> a[i].cena_za_kus;
  sort(a,a+N,cmp);

  for(int i=0;i<POCET_KUSU+1;i++)
    m[i]=INT_MAX;
  m[0]=0;

  for(int i=1;i<POCET_KUSU+1;i++)
    for(int j=0;(j<N)&&(a[j].pocet_kusu<=i);j++)
      if(m[i-a[j].pocet_kusu]<INT_MAX)
        m[i]=min(m[i],a[j].pocet_kusu*a[j].cena_za_kus+m[i-a[j].pocet_kusu]);

  if(m[POCET_KUSU]<INT_MAX)
    cout << "Reseni: " << m[POCET_KUSU] << endl;
  else
    cout << "Pozadovany pocet kusu neni mozne poskladat z dostupnych balicku" << endl;

  delete [] a;
  delete [] m;
}


[Reklama]

[vh]

Kouknul jsem na zadni jen zbezne, ale vypada to jako uplne typicka (ale strasne trivialni) uloha linearniho programovani.

[vokoun]

Kouknul jsem na zadni jen zbezne, ale vypada to jako uplne typicka (ale strasne trivialni) uloha linearniho programovani.

To bude proto, že ses kouknul jen zběžně.

[vh]

Hmm, jasny je tam jaksi jen jedna omezujici podminka priste se radeji budu koukat pozorneji

[Václav Zajíc]

Rekl bych, ze je to klasicka aplikace problemu batohu (jak narvat do batohu optimalni mnozstvi s ruznou vahou a dulezitosti)

[slowthinker]

Zadání:
V internetovém obchode je možno zakoupit zboží v různých baleních za různou cenu.
např.:
bal1 (1ks, 20kč/ks)
bal2 (5ks, 18kč/ks)
bal3 (10ks, 19kč/ks)
bal4 (50ks, 17kč/ks)

Zákazník požaduje např 78ks zboží a program by měl optimální počty balení vložit do košíku, aby to pro zázaníka bylo cenově nejvýhodnější.

Dle mého názoru je to jednoduché, a o žádný NP-úplný problém se nejedná:

Algoritmus bude postupně hledat ideální nákupy pro k ks zboží, kde k=1 až 78. Pro každé k si ideální nákup zapamatuje.
Známe-li ideální nákupy pro 1 ks až např. 50 ks ( I(1), I(2), I(3)... jsou ideální nákupy), zjistíme ideální nákup pro 51 ks jako nejlevnější z těchto nákupů:
1] jednotlivá balení (nákup je tvořen jedinou položkou, tedy jedním balením (dle zadání je to 1ks nebo 5ks nebo 10ks nebo 50ks)
2] spojení dvou ideálních nákupů  I(50) a I(1); dále I(49) a I(2); dále I(47) a I(3) atd.

(Důkaz: rozložíme-li ideální nákup pro k ks zboží na jakékoli dvě skupiny o počtech zboží k1, k2, kde k1+k2=k, jsou příslušné dva nákupy pro k1 a k2 také ideální. Nelze-li nákup rozložit, jedná se o nákup typu 1] )

[Ondřej Vaniš]

Zadání:
V internetovém obchode je možno zakoupit zboží v různých baleních za různou cenu.
např.:
bal1 (1ks, 20kč/ks)
bal2 (5ks, 18kč/ks)
bal3 (10ks, 19kč/ks)
bal4 (50ks, 17kč/ks)

Zákazník požaduje např 78ks zboží a program by měl optimální počty balení vložit do košíku, aby to pro zázaníka bylo cenově nejvýhodnější.

Dle mého názoru je to jednoduché, a o žádný NP-úplný problém se nejedná:

Algoritmus bude postupně hledat ideální nákupy pro k ks zboží, kde k=1 až 78. Pro každé k si ideální nákup zapamatuje.
Známe-li ideální nákupy pro 1 ks až např. 50 ks ( I(1), I(2), I(3)... jsou ideální nákupy), zjistíme ideální nákup pro 51 ks jako nejlevnější z těchto nákupů:
1] jednotlivá balení (nákup je tvořen jedinou položkou, tedy jedním balením (dle zadání je to 1ks nebo 5ks nebo 10ks nebo 50ks)
2] spojení dvou ideálních nákupů  I(50) a I(1); dále I(49) a I(2); dále I(47) a I(3) atd.

(Důkaz: rozložíme-li ideální nákup pro k ks zboží na jakékoli dvě skupiny o počtech zboží k1, k2, kde k1+k2=k, jsou příslušné dva nákupy pro k1 a k2 také ideální. Nelze-li nákup rozložit, jedná se o nákup typu 1] )

V tomto případě je to jednoduché ale zkuste to vypočítat např pro 1000ks to už je jiná.
Pak se dostaneme k tomuto a*k1+b*k2+c*k3+d*k4=k.
Takže opět NP-úplný problém :-/

[slowthinker]

Ale kdepak.
I pro 1000 ks bude optimální nákup hledán mezi spojeními DVOU nákupů s počtem ks <1000.
Časová náročnost algoritmu je kvadratická.

[Logik]

Máš a nemáš pravdu. To tvoje řešení je kvadratický a funguje, ale není kvadratický vzhledem k velikosti zadání - je to něco jako kdybys tvrdil, že řadit lze rychlejc než nlogn, protože radix sort.
Problém je v tom, že je to kvadratický vzhledem k chtěný ceně, tak je ale exponenciální vzhledem k velikosti vstupu (chtěný počet n se zapíše pomocí log n cifer).
Nicméně máš pravdu, že je to asi nejrozumější možný řešení. :-)

Více viz pseudopolinomiální algoritmy.

[slowthinker]

"chtěná cena" - ta je přece neznámá, chtěná cena je ta nejmenší možná.
Asi jsi měl na mysli, že algoritmus je kvadratický vzhledem k požadovanému počtu koupených kusů - s tím souhlasím.
"velikost vstupu" - to máš na mysli počet elementárních balení (4 balení (1, 5, 10 , 50 ks) v našem zadání)? Vzhledem k počtu elementárních balení je časová náročnost programu lineární (lineární kombinace, které se ve vnitřním cyklu porovnávají, se lineárně prodlužují).

Takže žádnou exponencionální náročnost nevidím, maximálně kubickou, pokud budou proměnné jak počet požadovaných kusů tak počet elementárních balení, a budeme předpokládat že rostou "stejně rychle".
Podle mě ale lze počet elementárních balení považovat za proměnnou veličinu pouze ve velmi speciálních případech. Rozhodně ne tehdy, pokud se musí nejprve nějaký obchodník rozhodnout, že nabídne k prodeji nové balení, a někdo je pak bude muset přidat ručně do systému. Ano tehdy, pokud budou balení a jejich ceny určovány automatizovaně - budou vypočteny třeba na základě cen na trhu, a to i pro velmi (neomezeně) velká balení.

[Ondřej Vaniš]

Algoritmus bude postupně hledat ideální nákupy pro k ks zboží, kde k=1 až 78. Pro každé k si ideální nákup zapamatuje.

A jakým způsobem zjistíš že je nákup ideální. To je práve základní zadání úlohy.
Ideálním nákupem je myslíš co? Kombinaci různých balení která má množství rovno k?