Carbó de reis X10514

El Nadal s’acosta. Aquest any hi ha hagut un augment significatiu en el nombre i gravetat de les trapelleries dels nens de tot el món, i els Reis Mags s’han adonat que amb el carbó que tenen en reserva no n’hi haurà prou. Per aquest motiu han decidit obrir la seva mina i extreure’n tot el carbó que es pugui en els dies que queden. Per fer-ho, disposen d’una borsa de $n$ miners i d’un pressupost de $b$ euros. Per cada miner $i$, es coneix el cost $c_{i}$ de contractar-lo, i la seva productivitat $p_{i}$ en l’extracció de carbó (mesurada en kilograms/dia). El que es vol és maximitzar la productivitat diària de carbó, subjecta al pressupost existent. Hi ha a més una altra restricció per motius de seguretat: l’ascensor que duu de l’entrada de la mina fins a la galeria ha de poder portar tots els miners alhora en cas d’evacuació. L’ascensor té un límit de pes $a$, i el pes del miner $i$ és $m_{i}$.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$, el nombre de miners, seguit de $b$, el pressupost, seguit de $a$, el límit de pes de l’ascensor. A continuació vénen $n$ tripletes de nombres $p_{i}$, $c_{i}$, $m_{i}$ que representen la productivitat, el cost i el pes del treballador $i$.

Podeu assumir que tots els nombres són naturals, que els diners es mesuren en euros, les productivitats en kilograms/dia i els pesos en kilograms. També podeu assumir que $1 \leq n \leq 500$, que $1 \leq p_{i} \leq 100$, que $1 \leq c_{i} \leq b \leq 50$, i que $1 \leq m_{i} \leq a \leq 200$.

Sortida

Per cada cas, escriviu la màxima productivitat diària que es pot aconseguir amb un subconjunt dels $n$ treballadors, amb un pressupost de $b$ euros i un ascensor amb límit de pes $a$.

Observació

Un algorisme de cerca exhaustiva hauria de ser massa lent per resodre aquest problema.