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 | 
2004-2016 BDG algoritmus szakkör