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
|