0/1 knapsack
Mediumdynamic programmingarray
Item i weighs weights[i] and is worth values[i]; the bag holds at most capacity. Each item is taken whole or not at all (at most once). Return the largest total value.
Example 1
Input: weights = [1,3,4,5], values = [1,4,5,7], capacity = 7 Output: 9
Weights 3 and 4 give value 9.
Example 2
Input: weights = [5], values = [10], capacity = 4 Output: 0
Constraints
- 1 ≤ n ≤ 100
- 1 ≤ weights[i] ≤ 1000
- 0 ≤ values[i] ≤ 1000
- 0 ≤ capacity ≤ 1000
Submit checks your solution against 8 tests, including hidden ones.
/**
* @param {int[]} weights
* @param {int[]} values
* @param {int} capacity
* @return {int}
*/
function knapsack(weights, values, capacity) {
}