„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
Visszavontam Arklur (vita | szerkesztései) szerkesztését (oldid: 167483) |
|||
| 74. sor: | 74. sor: | ||
===5. Feladat=== | ===5. Feladat=== | ||
A hátizsák probléma órán tanult algoritmusát futtattuk egy konkrét inputon, melyben 3 tárgy szerepel. Mi lehetett ez a konkrét input, ha az alábbi táblázat keletkezett? | A hátizsák probléma órán tanult algoritmusát futtattuk egy konkrét inputon, melyben 3 tárgy szerepel. Mi lehetett ez a konkrét input, ha az alábbi táblázat keletkezett? | ||
{| class="wikitable" border="5" | {| class="wikitable" border="5" | ||
| 125. sor: | 125. sor: | ||
|szöveg= | |szöveg= | ||
Az egyszerűség kedvéért a súly legyen kg, az érték pedig €. | |||
#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. | |||
##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. | |||
##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. | |||
##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. | |||
Tehát végeredményben a megoldás: | |||
*1-es csomag (€10, 4kg) | |||
*2-es csomag (€5, 2kg) | |||
*3-as csomag (€13, 4kg) | |||
}} | }} | ||