Projects for a district
A district is choosing which courtyards to improve this year. There are n projects: project i costs ci tenge and puts vi courtyards in order. A project is done whole or not at all, and no courtyard is in two projects. The budget is B tenge. How many courtyards can be improved for this money?
Input
The first line holds n and B (1 ≤ n ≤ 100, 0 ≤ B ≤ 1011). Then come n lines: the cost of a project ci in tenge and the number of courtyards vi (1 ≤ ci ≤ 109, 1 ≤ vi ≤ 100).
Output
The largest number of courtyards that can be improved without exceeding the budget.
Examples
Example 1
4 1000 600 13 500 10 500 10 80 1
20
Example 2
2 50 90 5 60 3
0
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
This is a knapsack: the budget is the capacity, the cost the weight, the courtyards the usefulness. How many cells will the ordinary table “the first i projects, b tenge” have if the budget is a hundred billion?
2Hint 2
Which quantity in the input is small? A project has at most a hundred courtyards, and there are at most a hundred projects. What if the columns of the table are not money but courtyards?
3The idea
Turn the table round: cheapest[v] is the least money for which exactly v courtyards can be improved. There are at most 100 · 100 = 104 courtyards in all, and the table is small however much the projects cost. The transition is the same as in the 0-1 knapsack, only with a minimum: cheapest[v] = min(cheapest[v], cheapest[v − vi] + ci). The answer is the largest v for which cheapest[v] ≤ B.
4Walkthrough
At first cheapest[0] = 0 and the rest are infinity: no project has been considered yet. Add the projects one at a time, going through the array from large v to small, so that a project is not counted twice. Sums of money go up to 1011: Go needs int64, and “infinity” should be taken with a margin so that adding a cost to it does not overflow.
Recall pseudo-polynomial time: the time of a knapsack depends on the size of the numbers in the dimension along which the table is built. Usually that is the capacity, but the table can be built along either of the two quantities, weight or value. Choose the one where the numbers are small.
4+Solution
5Complexity
O(n · Σvi), at most 106 steps, and O(Σvi) memory.
6Common mistakes
- A table by money. A hundred billion cells do not fit in memory. It passes only the examples.
- Greed by courtyards per tenge. Fails the first example: the same catch as in the ordinary knapsack.
- Overflow. The sum of the costs of a hundred projects goes up to 1011 and does not fit in 32 bits.