Fill the Cargo Hold
A cargo plane can carry a total weight of at most capacity. Crate i weighs weights[i] and is worth values[i]. Each crate is either loaded whole or left behind, and there is only one of each.
Return the largest total value that can be loaded.
Example 1
Input: weights = [1,3,4,5], values = [1,4,5,7], capacity = 7 Output: 9 Explanation: Load the crates of weight 3 and 4 for value 4 + 5 = 9.
Example 2
Input: weights = [2,2,3], values = [3,3,5], capacity = 4 Output: 6 Explanation: Two weight-2 crates, value 6.
Constraints
- 0 <= weights.length == values.length <= 100
- 1 <= weights[i], values[i] <= 1000
- 0 <= capacity <= 10^4
Hint 1
Let best[c] be the top value achievable with total weight at most c.
Hint 2
Process crates one at a time and update best[] from high c to low c so each crate is used at most once.
Discussion 0
Join free to post in the discussion.
Good practice for: Backend Developer, Data Scientist, Data Engineer, Cloud Engineer, Blockchain Developer, Machine Learning Engineer
Run checks your code on 3 sample tests. Submit runs all 9 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.