SPOJ: 4301. Tables

Byteman works as a carpenter. He has just received an order for s pine-wood tables. Although he has plenty of pine-wood boards in his workshop, he has just run out of screws. Therefore he needs to walk to the warehouse and bring back some boxes with screws. What is the minimum number of boxes that he needs to bring in order to have enough screws to make the tables?

Problem: Sphere Online Judge (SPOJ) – Problem AE1B

Solution: That’s a nice application for an greedy algorithm, i.e. you grab the largest values successively. This yields the optimal solution in this case because we don’t need to find exactly X screws. It’s sufficient to find at least X screws.

inp1 = raw_input()
inp2 = raw_input()


numBoxes, screwsPerTable, tables = inp1.split()

boxes = inp2.split()

numBoxes = int(numBoxes)
screwsPerTable = int(screwsPerTable)
tables = int(tables)
boxes = map(int, boxes)

boxes.sort()
boxes.reverse()

needed = tables * screwsPerTable

i = 0
while needed > 0:
    needed -= boxes[i]
    i += 1

print i