Problém batoha - História úprav

Juraj na 15:35, 24. máj 2010

2010-05-24T15:35:19Z

Juraj: /* Iné prístupy k riešeniu */

2010-04-08T17:49:00Z

Iné prístupy k riešeniu

Juraj na 17:47, 8. apríl 2010

2010-04-08T17:47:11Z

Amonatrix na 16:59, 8. apríl 2010

2010-04-08T16:59:08Z

Jumanji na 16:45, 8. apríl 2010

2010-04-08T16:45:44Z

Jumanji na 16:45, 8. apríl 2010

2010-04-08T16:45:01Z

Jumanji na 16:44, 8. apríl 2010

2010-04-08T16:44:13Z

Jumanji na 16:38, 8. apríl 2010

2010-04-08T16:38:21Z

Jumanji na 16:32, 8. apríl 2010

2010-04-08T16:32:53Z

Jumanji na 16:32, 8. apríl 2010

2010-04-08T16:32:23Z

@@ Riadok 1: / Riadok 1: @@
-[[Kategória:Programovanie]][[Kategória:Algoritmy]]
+[[Kategória:Algoritmy a programovanie]]
 == Formulácia problému ==
 Zlodej, ktorý vylomil zámok na trezore, zistil, že je naplnený n vecami rôznych veľkostí a rôznej ceny. Na lup má ale len batoh kapacity k, problém batohu je práve nájsť takú kombináciu vecí z trezoru, aby sa mu zmestila do batoha a bola čo možno najcennejšia.

@@ Riadok 46: / Riadok 46: @@
 == Iné prístupy k riešeniu ==
 '''Greedy algoritmus:''' tento prístup spočíva v tom, že keďže zlodej je veľmi chamtivý (greedy), tak berie predmety v klesajúcom poradí podľa ich ceny. Skončí s batohom, ktorý nie je úplne zaplnený. To, že batoh nie je úplne zaplnený ešte neznamená, že riešenie nie je správne, ale v mnohých prípadoch je to hlavnou príčinou.
 '''
-Brute force:''' iný zlodej skúsil vypočítať všetky možnosti výberu vecí. Všetkých možností je ale 2n, takže zložitosť tohto algoritmu by bola exponenciálna.
+'''Brute force:''' iný zlodej skúsil vypočítať všetky možnosti výberu vecí. Všetkých možností je ale 2n, takže zložitosť tohto algoritmu by bola exponenciálna.
 == Zložitosť algoritmu ==
 Časová zložitosť algoritmu závisí od veľkosti tabuľky.

@@ Riadok 1: / Riadok 1: @@
 == Formulácia problému ==
 Zlodej, ktorý vylomil zámok na trezore, zistil, že je naplnený n vecami rôznych veľkostí a rôznej ceny. Na lup má ale len batoh kapacity k, problém batohu je práve nájsť takú kombináciu vecí z trezoru, aby sa mu zmestila do batoha a bola čo možno najcennejšia.
 == Riešenie problému ==
 Kľúčové pozorovanie, ktoré vedie k peknému riešeniu: Ak máme maximálne dosiahnuteľné ceny lupu pre všetky celočíselné kapacity batohu pomocou prvých k predmetov, ľahko spočítame maximálne ceny pre prvých k+1 predmetov. A to tak, že skúsime pridať k + 1 - vý predmet do batohu s k predmetmi a kapacitou nižšou o hmotnosť tohto predmetu. Predmet nepridáme, pokiaľ cena takého lupu nie je vyššia od ceny lupu z prvých k predmetov v batohu s rovnakou kapacitou. Prvý predmet je možné vložiť do batohu s kapacitou rovnou aspoň hmotnosti predmetu a cena lupu je maximálna možná. Pre ďalšie predmety to plynie z indukcie.
@@ Riadok 15: / Riadok 14: @@
 Prvý riadok je taktiež naplnený nulami, zodpovedá to totiž batohu so žiadnym vloženým predmetom.
 Tabuľku vypĺňame zľava doprava a zhora nadol. Do jednotlivých buniek vpisujeme hodnotu tak, že sa pozrieme na aktuálnu nosnosť batohu, potom na hmotnosť predmetu a jeho cenu a tiež sa musíme pozrieť na aktuálnu hodnotu vecí v batohu.
 [[Súbor:Batoh1.jpg|framed|center|]]
 - V uvedenom príklade začíname s batohom so žiadnym vloženým predmetom. Tým pádom hodnota batohu je nulová.
@@ Riadok 30: / Riadok 27: @@
 Označme W={w1,w2,..wn} ako sadu hmotností a V={v1,v2,..vn} ako sadu hodnôt predmetov. Nech k je cieľová kapacita, predstavujúca najväčšiu hmotnosť vecí, ktorú batoh dokáže uniesť. Riešením problému je:
-----
+<math>\max \left( \sum\limits_{i}{\left\{ 0,1 \right\}{{v}_{i}}} \right)</math>
-[[Súbor:Vzorec.jpg]]	 a     [[Súbor:Vzorec1.jpg]]
+<math>\max \left( \sum\limits_{i}{\left\{ 0,1 \right\}{{w}_{i}}} \right)</math>
 T. j. riešenie s maximálnou hodnotou a minimálnou váhou. Množina {0,1} indikuje, či predmet je v batohu alebo nie.
 Tento problém by sa dal riešiť rekurzívnou metódou. Táto metóda by bola ale veľmi neefektívna, lebo niektoré podproblémy by sa riešili viackrát.
 Označme T[i][j] maximálnu cenu batohu s i predmetmi a nosnosťou o veľkosti j. Pri dynamickom programovaní teda využijeme tento vzorec:
-  ak j – váhy[i-1] < 0, potom T[i][j] =T [i - 1][j],
+<source lang="pascal">
-  inak T[i][j] = max (T[i-1,j], hodnoty[i-1] + T[i-1,
+  ak (j – váhy[i-1]) < 0  potom
- j - váhy[i-1] ), pričom hodnoty je pole hodnôt jednotlivých predmetov a váhy je pole váh jednotlivých predmetov.
+    T[i][j] = T[i - 1][j]
   inak
+    T[i][j] = max ( T[i-1,j] , hodnoty[i-1] + T[i-1, j - váhy[i-1] )
+              pričom hodnoty je pole hodnôt jednotlivých predmetov a váhy je pole váh jednotlivých predmetov.
 == Iné prístupy k riešeniu ==
+'''Greedy algoritmus:''' tento prístup spočíva v tom, že keďže zlodej je veľmi chamtivý (greedy), tak berie predmety v klesajúcom poradí podľa ich ceny. Skončí s batohom, ktorý nie je úplne zaplnený. To, že batoh nie je úplne zaplnený ešte neznamená, že riešenie nie je správne, ale v mnohých prípadoch je to hlavnou príčinou.
-Greedy algoritmus: tento prístup spočíva v tom, že keďže zlodej je veľmi chamtivý (greedy), tak berie predmety v klesajúcom poradí podľa ich ceny. Skončí s batohom, ktorý nie je úplne zaplnený. To, že batoh nie je úplne zaplnený ešte neznamená, že riešenie nie je správne, ale v mnohých prípadoch je to hlavnou príčinou.
+'''
+Brute force:''' iný zlodej skúsil vypočítať všetky možnosti výberu vecí. Všetkých možností je ale 2n, takže zložitosť tohto algoritmu by bola exponenciálna.
 == Zložitosť algoritmu ==
 Časová zložitosť algoritmu závisí od veľkosti tabuľky.
 Máme tu 2 faktory:
-n + 1 riadkov, kde n je počet predmetov a
+*n + 1 riadkov, kde n je počet predmetov a
-k + 1 stĺpcov, kde k je maximálna kapacita batohu.
+*k + 1 stĺpcov, kde k je maximálna kapacita batohu.
 Čiže časová zložitosť tohto algoritmu je O(k*n).
 Číslo k ale nie je konštanta, môže byť oveľa väčšie ako počet vecí, ktoré môžeme do batohu vložiť.
 Tento algoritmus má teda zložitosť rovnú pseudo – polynomiálnemu času.
 == Využitie ==
 Tento problém sa využíval ako základ pre kryptografický systém (ktorý bol odvtedy prelomený).
 Ďalej sa využíva pri problémoch, kde riešenie závisí na výbere nejakého počtu vecí, ktorých hodnota je maximálna (alebo minimálna), a ktorých váha je rovná cieľovej váhe.
 == Program v jazyku C++ ==
+<source lang="c" line>
 const n=3;
- const n=3;
+void greedy(double M,double W[n],double C[n],double X[n])
- void greedy(double M,double W[n],double C[n],double X[n])
- { double Z=M;
+  double Z=M;
- int i;
+  int i;
- for (i=0; i<n; i++) {
+  for (i=0; i<n; i++)
- if(W[i]>Z)a
- break;
+     if(W[i]>Z)
- X[i]=1;
+       break;
- Z=Z-W[i];
+     X[i]=1;
+     Z=Z-W[i];
+  }
- int main()
+int main()
-−
+{
- double W[n]={10,12,16}, C[n]={60,70,80}, X[n]={0,0,0};
+  double W[n]={10,12,16}, C[n]={60,70,80}, X[n]={0,0,0};
- greedy(20,W,C,X);
+  greedy(20,W,C,X);
- double p=0;
+  double p=0;
- for (int i=0 ;i<n; p+=X[i]*C[i],i++)
+  for (int i=0 ;i<n; p+=X[i]*C[i],i++)
- cout<<i<<"\t"<<W[i]<<"\t"<<C[i]<<"\t"<<X[i]<<endl;
+    cout<<i<<"\t"<<W[i]<<"\t"<<C[i]<<"\t"<<X[i]<<endl;
   cout<<"celkom:"<<p<<endl;
-  system("pause"); }
+  system("pause");

← Staršia verzia		Verzia zo dňa a času 16:59, 8. apríl 2010
Riadok 17:		Riadok 17:


−	[[Súbor:Batoh1.jpg]]	+	[[Súbor:Batoh1.jpg\|framed\|center\|]]

@@ Riadok 1: / Riadok 1: @@
-== Formulácia problému: ==
+== Formulácia problému ==
 Zlodej, ktorý vylomil zámok na trezore, zistil, že je naplnený n vecami rôznych veľkostí a rôznej ceny. Na lup má ale len batoh kapacity k, problém batohu je práve nájsť takú kombináciu vecí z trezoru, aby sa mu zmestila do batoha a bola čo možno najcennejšia.
-== Riešenie problému: ==
+== Riešenie problému ==
 Kľúčové pozorovanie, ktoré vedie k peknému riešeniu: Ak máme maximálne dosiahnuteľné ceny lupu pre všetky celočíselné kapacity batohu pomocou prvých k predmetov, ľahko spočítame maximálne ceny pre prvých k+1 predmetov. A to tak, že skúsime pridať k + 1 - vý predmet do batohu s k predmetmi a kapacitou nižšou o hmotnosť tohto predmetu. Predmet nepridáme, pokiaľ cena takého lupu nie je vyššia od ceny lupu z prvých k predmetov v batohu s rovnakou kapacitou. Prvý predmet je možné vložiť do batohu s kapacitou rovnou aspoň hmotnosti predmetu a cena lupu je maximálna možná. Pre ďalšie predmety to plynie z indukcie.
@@ Riadok 48: / Riadok 48: @@
-== Iné prístupy k riešeniu: ==
+== Iné prístupy k riešeniu ==
 Greedy algoritmus: tento prístup spočíva v tom, že keďže zlodej je veľmi chamtivý (greedy), tak berie predmety v klesajúcom poradí podľa ich ceny. Skončí s batohom, ktorý nie je úplne zaplnený. To, že batoh nie je úplne zaplnený ešte neznamená, že riešenie nie je správne, ale v mnohých prípadoch je to hlavnou príčinou.
@@ Riadok 56: / Riadok 56: @@
-== Zložitosť algoritmu: ==
+== Zložitosť algoritmu ==
 Časová zložitosť algoritmu závisí od veľkosti tabuľky.
@@ Riadok 68: / Riadok 68: @@
-== Využitie: ==
+== Využitie ==
 Tento problém sa využíval ako základ pre kryptografický systém (ktorý bol odvtedy prelomený).
@@ Riadok 76: / Riadok 76: @@
-== Program v jazyku C++: ==
+== Program v jazyku C++ ==

@@ Riadok 21: / Riadok 21: @@
 - V uvedenom príklade začíname s batohom so žiadnym vloženým predmetom. Tým pádom hodnota batohu je nulová.
- Pokračujeme ďalej druhým riadkom postupne v smere rastúcej kapacity.
+Pokračujeme ďalej druhým riadkom postupne v smere rastúcej kapacity.
 Celý riadok môžeme zaplniť touto hodnotou (riadiac sa podľa vzorca, ktorý je uvedený).
 - Prvý predmet má hmotnosť 1, teda sa vojde do batohu danej kapacity, čiže môžeme napísať, že cena takého batohu bude rovná cene predmetu.

@@ Riadok 81: / Riadok 81: @@
   X[i]=Z/W[i];
+  }
   int main()