ACM RTK - 2. skupina

Ovce

Novozelandski kmet ima n ovac. V času t morajo biti vse ovce ostrižene, saj bo takrat odprodal volno. Ima seznam m strižcev. Za vsakega ima dva podatka:

• p_i je plačilo, ki ga zahteva i-ti strižec za striženje ene ovce;
• t_i je čas, ki ga porabi i-ti strižec za striženje ene ovce.

Aparat za striženje pokuri za c denarnih enot elektrike na časovno enoto. Opiši postopek, ki iz teh podatkov ugotovi, kolikšen je najmanjši znesek, ki ga bo kmet plačal za striženje (najem delovne sile + elektrika), če delovno silo izbira optimalno. Vsi strižci lahko delajo hkrati in vsak ima svoj aparat za striženje. Tisti, ki začne striči ovco, jo mora tudi dokončati. Na voljo bo vedno dovolj delavcev, da bodo lahko v danem času ostrigli vse ovce.

Primer: recimo, da imamo n = 5 ovac, t = 12 enot časa, ceno elektrike c = 1 in dva strižca: enegas p₁ = 6, t₁ = 2 (drag, a hiter) in enega s p₂ = 2, t₂ = 5 (počasen, a cenejši). Potem se izkaže, da je najmanjši skupni strošek striženja enak 38 (dosežemo ga, če prvi strižec ostriže tri ovce, drugi pa dve).

PDF besedilo.