„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
| 141. sor: | 141. sor: | ||
##Így csak a €13 jöhet szóba, ami jó megoldás lesz. | ##Így csak a €13 jöhet szóba, ami jó megoldás lesz. | ||
{{Rejtett | |||
''Avagy kicsit gépiesebb megoldás:'' | |mutatott=''Avagy kicsit gépiesebb megoldás:'' | ||
|szöveg= | |||
<br> | |||
Jelölje <math> T[s,cs]</math> a táblázat <math>[s,cs]</math> celláját, továbbá <math> V_3</math> a 3. csomag értékét, <math> S_3</math> pedig a súlyát.<br><br> | Jelölje <math> T[s,cs]</math> a táblázat <math>[s,cs]</math> celláját, továbbá <math> V_3</math> a 3. csomag értékét, <math> S_3</math> pedig a súlyát.<br><br> | ||
Tudjuk, hogy <math> T[s,cs]=max\left \{ T[s,cs-1];V_i+T[s-S_i,cs-1] \right \}</math>, ami ebben az esetben:<br><br> | Tudjuk, hogy <math> T[s,cs]=max\left \{ T[s,cs-1];V_i+T[s-S_i,cs-1] \right \}</math>, ami ebben az esetben:<br><br> | ||
<math> T[4,3]=max\left \{ T[4,2];V_3+T[4-S_3,2] \right \} \rightarrow 13=max\left \{ 10;V_3+T[4-S_3,2] \right \}</math>, amiből következik, hogy:<br><br> | <math> T[4,3]=max\left \{ T[4,2];V_3+T[4-S_3,2] \right \} \rightarrow 13=max\left \{ 10;V_3+T[4-S_3,2] \right \}</math>, amiből következik, hogy:<br><br> | ||
<math> 13=V_3+T[4-S_3,2] \rightarrow V_3 = 13-T[4-S_3,2]\Rightarrow\Rightarrow S_3=4, V_3=13</math> (Átgondolható, hogy a 3. csomag súlya nem lehet 1,2 vagy 3kg). | <math> 13=V_3+T[4-S_3,2] \rightarrow V_3 = 13-T[4-S_3,2]\Rightarrow\Rightarrow S_3=4, V_3=13</math> (Átgondolható, hogy a 3. csomag súlya nem lehet 1,2 vagy 3kg). | ||
}} | |||
Tehát végeredményben a megoldás: | Tehát végeredményben a megoldás: | ||
*1-es csomag (€10, 4kg) | *1-es csomag (€10, 4kg) | ||