NézetNyomtat

Fűrészmalom (Megoldás)
Címkék > Feladat

Fűrészmalom

Feladat

A folyó mentén kitermelt fát N helyen gyűjtik össze és szállítják a folyón lefelé úsztatva az első gyűjtőhelyre, ahol fűrészmalomban végzik a feldolgozást. A vállalat elhatározta, hogy további fűrészmalmot állít üzembe néhány gyűjtőhelyen. Minden gyűjtőhelyről a fát a folyón lefelé haladva az első fűrészmalomba fogják szállítani. A szállítási költség a megtett távolság és a tömeg szorzata. Ismerjük az egyes gyűjtőhelyek elhelyezkedését (az elsőtől vett távolságot km-ben) és azt, hogy mennyi fa keletkezik évente az egyes gyűjtőhelyeken. Kiszámítandó, hogy hova kell telepíteni az új fűrészmalmokat, hogy a szállítási összköltség a lehető legkisebb legyen.

Bemenet

Az első sor a gyűjtőhelyek N számát és az építendő új malmok K számát tartalmazza.
Ezután N sorban egy-egy számpár következik: az i. gyűjtőhely távolsága az elsőtől, majd az i. gyűjtőhelyen egy évben kitermelt fa tömege.

Kimenet

A minimális összköltséget kell megadni, és azt, hogy ehhez melyik gyűjtőhelyeken kell beindítani az új malmokat.

Példa

i 1 2 3 4 5 6 7 8 9 10 11 12 13 14
táv[i] 0 2 3 6 7 20 22 34 35 44 57 66 88 100
fa[i] 1 2 3 44 5 6 33 18 9 10 11 2 13 44

válaszok

1 új malom esetén: minimum = 3812; új malom: 13
2 új malom esetén: minimum = 1986; új malmok: 7 13
3 új malom esetén: minimum = 1332; új malmok: 6 8 13
4 új malom esetén: minimum = 804; új malmok: 6 8 13 14

Teszadatok

Bemenet

Kimenetek