Adott egy K kapacitású hátizsák és N darab tárgy, amelyek tömege m₁, m₂, ... m_N, értéke pedig e₁, e₂,.. e_N. 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.  

Í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.

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.

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.

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

A feladat forrása: közismert feladat, (tesztadatok: Coursera, Discrete Optimization)

Algoritmusok: dinamikus programozás, lokális keresés