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 ≤ n ≤ 500, que 1 ≤ p_i ≤ 100, que 1 ≤ c_i ≤ b ≤ 50, i que 1 ≤ m_i ≤ a ≤ 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.