Programozás‎ > ‎Feladatok‎ > ‎

Teher-fuvar

Szállítmányozási vállalkozó vagy és meg kell szervezned teherautód optimális kihasználását. Teherautóddal egy irányban haladsz az úton, mely mentén települések sorakoznak. Minden településen egy adott tömegű csomag várakozik rád, melynek elszállításáért a tulajdonosa adott összeget hajlandó fizetni. Minden csomagot az út legvégén található kikötőig kell elszállítanod, és sosem fordulhatsz vissza, tehát a megadott sorrendben látogatod végig a településeket

Feladat

Írj programot ami meghatározza a legnagyobb elérhető összhasznot a megadott bemenethez. 

Bemenet

Az első sor tartalmazza a települések 1<=N<=50 számát és a teherautód 1<=K<=200 teherbírását. Az utána következő N sor pedig E és S számokat, ahol 1<=E<=100 a felajánlott fizetség, 1<=S<=200 pedig az áru súlya. 

Kimenet

Az első sora legyen az elérhető legnagyobb haszon, utána pedig következzenek azon települések sorszámai, ahol árut veszünk fel. 

Példa

Bemenet  Kimenet
10 200 23 43 32 12 21 43 32 43 21 43 21 65 21 54 54 65 12 23 34 56
164 2 4 8 9 10


Tesztadatok

Címkék

A feladat forrása: ???
Algoritmusok: dinamikus programozás

megoldás