Orders for a courier
A bicycle courier carries orders in a backpack that holds W grams. The app shows n orders: each has a weight in grams and a payment in tenge. An order is taken whole or not at all. Which orders should be taken to earn as much as possible?
If there are several best sets, print any.
Input
The first line holds n and W (1 ≤ n ≤ 100, 1 ≤ W ≤ 104). Then come n lines: the weight of an order wi in grams and the payment ci in tenge (1 ≤ wi ≤ 104, 1 ≤ ci ≤ 105). The orders are numbered from one in input order.
Output
The first line holds the largest total payment. The second, how many orders to take. The third, their numbers separated by spaces (the line is empty if nothing is taken).
Examples
Example 1
4 10000 6000 1300 5000 1000 5000 1000 800 100
2000 2 2 3
Example 2
2 500 900 2000 600 700
0 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
The first thought is to take orders in decreasing order of payment per gram. Check it on the first example: a 10 kg backpack, an order of 6 kg for 1300 tenge and two orders of 5 kg for 1000.
2Hint 2
Consider the last order. If it is not taken, the answer is the best of the first n − 1 orders with the same room. If it is, its payment plus the best of the first n − 1 orders in the remaining room. Which answers do you need to know in advance for this?
3The idea
This is the 0-1 knapsack. best(i, x) is the largest payment from the first i orders with x grams of room, and best(i, x) = max(best(i − 1, x), ci + best(i − 1, x − wi)). To name the orders themselves afterwards, remember for each cell whether order i is taken in it, and go back from (n, W).
4Walkthrough
The numbers are conveniently kept in one row of length W + 1 updated from right to left: then best[x − w] at the moment of reading still refers to the previous order, and each order is taken at most once. The row will not keep the decisions “is order i taken in cell x”, so keep a separate bit array for each order for them, n·(W + 1) bytes, about a megabyte.
The path back: stand at x = W and go over the orders from the last. If cell x is marked in order i’s row, the order is taken, and x decreases by its weight. The mark is set only when the order improved the cell compared with the answer without it, so this gives exactly the set that produced the number in the last cell.
In the first example greed takes the 6 kg order, which has the best payment per gram, 1300 tenge, and nothing else big fits: 1300 + 100 = 1400. But the two 5 kg orders give 2000.
4+Solution
5Complexity
O(n·W) time, a million cells, and O(n·W) memory for the marks.
6Common mistakes
- Greed by payment per gram. Fails the first example.
- One row from left to right. Then best[x − w] may already contain this same order, and it is taken several times.
- Recovering from one row of numbers. At the end the row holds answers only for all orders together; there is nothing to compare “with the order and without” against: you need the whole table or the marks.