You are packing for a hike. Item i weighs weights[i] kilograms and is worth values[i] comfort points. Your pack holds at most capacity kilograms, and each item can be packed at most once. Return the largest total comfort you can carry.
Examples
Input: weights = [3, 4, 2], values = [30, 50, 15], capacity = 6
Output: 65
Explanation: pack the items weighing 4 and 2.
Input: weights = [5], values = [10], capacity = 4
Output: 0
Constraints
0 <= len(weights) == len(values) <= 1001 <= weights[i] <= 2000,0 <= values[i] <= 10**40 <= capacity <= 2000- Trying every subset (up to
2**100) is out of the question; aim for O(n * capacity).
Goals
- Build a table indexed by item and remaining capacity
- Use each item at most once by scanning capacities downwards