Programozás‎ > ‎Feladatok‎ > ‎

Hátizsák probléma

Adott egy K kapacitású hátizsák és N darab tárgy, amelyek tömege m1, m2, ... mN, értéke pedig e1, e2,.. eN. Szeretnénk a legtöbb értéket bepakolni a hátizsákba, anélkül, hogy túllépnénk a hátizsák kapacitását.  


Feladat

Írjunk programot, ami megadja, hogy legfeljebb mennyi érték fér a hátizsákba! (Az érték a bepakolt tárgyak értékének összege.) További kérdés: adjuk is meg, hogy melyik tárgyakat kell bepakolni a hátizsákba az optimális érték eléréséhez.

Bemenet

A bemenet első sora a tárgyak számát és a hátizsák kapacitását tartalmazza. Ezután minden sorban egy tárgy leírása következik: először a tárgy értéke, utána a tárgy tömege.

Kimenet

Az első sorbába a maximálisan bepakolható értéket kell kiírni. A második sor annyi számból áll, ahány tárgyunk van. A bepakolt tárgyak helyére írjunk 1-et, a kihagyottak helyére 0-t.

Példa

Bemenet  Kimenet
5 15
4 12
2 1
10 4
1 1
2 2
15
0 1 1 1 1


Tesztadatok

Címkék

A feladat forrása: közismert feladat, (tesztadatok: Coursera, Discrete Optimization)
Algoritmusok: dinamikus programozás, lokális keresés