„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés

← Régebbi szerkesztés Újabb szerkesztés →

VizuálisWikiszöveges

@@ 137. sor: / 137. sor: @@
 #Az első sor alapján az 1-es csomag értéke €10, súlya 4kg.
 #A második sor alapján a 2-es csomag értéke €5, súlya 2kg.
-#A 3. sornál kicsit rafkósnak kell lenni. Leírhatnám egyből a megoldást, de talán több értelme van, ha a logikai zsákutcákat is leírom.
+#A 3. lépésben 2 lehetőségünk van, a 3. csomag értéke vagy 13-5=€8, vagy 13-0=€13.
-##Először gondolhatnánk arra, hogy a [4,3]-as cella 10+3 formában áll elő, így a 3-as csomag értéke €3. Viszont így a súlyának 0kg-nak kéne lennie, ami nyílván fatal error.
+##€8 nem lehet, mert akkor a súlya 2kg lenne, de akkor a [2,3] cellába 8 lenne, nem 5.
-##Második gondolatunk az lehetne, hogy akkor 5+8 formában áll elő, így a 3-as csomag értéke €8. Súlya ekkor 2kg kellene legyen, viszont akkor a [2,3]-as cellába 8-nak, és nem 5-nek kéne szerepelnie, tehát ez se jó megoldás.
+##Így csak a €13 jöhet szóba, ami jó megoldás lesz.
-##Harmadik ötletnek nagyon más nem jöhet szóba, hogy akkor a 3-as csomag értéke €13, súlya pedig 4kg. És ha leellenőrizzük, látszik, hogy ez lesz a jó megoldás.
+''Avagy kicsit gépiesebb megoldás:''<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>
+<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).
 Tehát végeredményben a megoldás: