The problem
A bag holds capacity kg. Each item is a pair (weight, value), and any part of an item may be taken: x kg of an item is worth x * value / weight. Lesson 1 worked out the largest value. Here, return the plan itself: a list with one number per item, in the order the items are given, saying how many kilograms of that item go in the bag.
how_much(8, [(5, 10), (4, 7), (3, 3), (2, 5)])
# [5, 1, 0, 2]: all of the first and last items,
# 1 kg of the second; worth 10 + 1.75 + 5 = 16.75
Each amount must be between 0 and its item’s weight, and the amounts together must fit in the bag. Any plan with the largest value passes: the tests report the value of your plan (compared to 9 significant figures), or what is wrong with it. Every weight is a whole number of at least 1, every value a whole number of at least 0, and capacity is at least 0.
Limits
- Up to 200,000 items. Aim for O(n log n).
Builds on GRDY-1 The greedy choice.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | Everything fits | Not run | |
| 3 | Cut the only item | Not run | |
| 4 | An empty bag | Not run | |
| 5 | No items | Not run | |
| 6 | Valuable but heavy | Not run | |
| 7 | Light but cheap | Not run | |
| 8 | Amounts in the order given | Not run | |
| 9 | Items worth nothing | Not run | |
| 10 | 200,000 items | Not run |