The capsule's cargo hold
- O(2ⁿ) · Legendary
- Full plan
- Python
- JavaScript
- recursion
- lists
- comparisons
Problem
The return capsule has a small cargo hold and a weight limit that is not up for discussion. Commander Farid Benali has to decide which of the station's experiments go down to Earth and which stay up there. An experiment cannot be split: it travels whole or it does not travel. Write a function that takes weights and points, two lists of positive whole numbers of the same length (experiment i weighs weights[i] kilos and is worth points[i] science points; both may be empty), and limit, a whole number of 0 or more. Return a whole number: the highest total of points you can load without the total of their weights going over limit. Reaching the limit exactly is fine. With weights [5, 4, 3], points [10, 7, 7] and limit 7: the 5-kilo one is worth the most, but once it is in nothing else fits and you are stuck at 10; with the 4-kilo and 3-kilo ones you get 14, so it returns 14. With weights [2, 3, 4], points [3, 4, 5] and limit 1 nothing fits: it returns 0.
Examples
The example
[5, 4, 3], [10, 7, 7], 7 → 14
Nothing fits
[2, 3, 4], [3, 4, 5], 1 → 0
The best value per kilo is not worth it
[1, 10], [2, 15], 10 → 15
Everything fits
[2, 2, 3], [4, 5, 6], 10 → 15
Besides these, the challenge has hidden tests that are revealed when you submit your solution.
You start with this
Python
def load(weights, points, limit):
passJavaScript
function load(weights, points, limit) {
}It opens in your browser, with the editor and the tests. This challenge is part of the full plan; the O(1) and O(log n) ones are free.