Technikák összehasonlítása II.
Backtraking / Greedy
Feladatok:
1. Egy üzletben n tárgy (áru) található, amelyeknek ismert az áruk és a súlyuk. Az árakat az a[1..n], a súlyokat a g[1..n] tömbben tároljuk, ahol a[i], g[i] (i = 1, n) természetes számok és rendre a tárgyak árait illetve súlyaikat jelölik. Írjunk programot, mey meghatározza, hogy egy tolvaj mely tárgyakat fogja magával vinni, ha azt szeretné, hogy a lehető legnagyobb nyereséggel távozzon az üzletből, tudva azt, hogy hátizsákja legtöbb G súlyt bír meg. Két esetet különböztetünk meg: a tárgyak feldarabolhatóak, illetve mikor nem..

Például:
Bemenet: N = 4, G = 5, g[1..4] = {2, 1, 3, 1}, a[1..4] = {5, 2, 4, 1}
Kimenet: (1, 1, 2/3, 0), melynek jelentése: az első és második tárgyat egészében, a harmadiknak pe­dig 2/3 része kerül a hátizsákba (a negyedik árú az üzletben marad). Ez 29/3 egység nyereséget jelent.

Greedy stratégia, alkalmazható, az első esetben: rendezzük a tárgyakat ár/súly szerint csökkenő sorrendbe, mely megadja az elvitt tárgyak sorrendjét is. Az első olyan tárgyból, mely nem fér be egészen a hátizsákba levágunk annyit, hogy azzal megteljen a hátizsák.

Backtraking stratégia, alkalmazható a második esetben: meghatározzuk az összes n elemű részsorozatot és kiválasztjuk azt, amelyik maximális összegű. A hatékonyság növelése érdekében csak olyan részsorozatot generáljunk ki, mely esetében a súlyok összege nem haladja meg a G-t.