0/1 Knapsack

Given an array of item weights, an array of item values, and a knapsack capacity W, determine the maximum value that can be obtained by selecting items such that the total weight does not exceed W. Each item can only be used once.

Examples

Example 1:

Input: weights = [1,2,3], values = [6,10,12], W = 5

Output: 22

Explanation: Select items with weights 2 and 3 (total weight = 5), giving values 10 + 12 = 22.

Example 2:

Input: weights = [1,3,4,5], values = [1,4,5,7], W = 7

Output: 9

Explanation: Select items with weights 3 and 4 (total weight = 7), giving values 4 + 5 = 9.

Example 3:

Input: weights = [2,3,4], values = [3,4,5], W = 5

Output: 7

Explanation: Select items with weights 2 and 3 (total weight = 5), giving values 3 + 4 = 7.

Constraints

• 1 <= weights.length <= 200
• weights.length == values.length
• 1 <= weights[i] <= 1000
• 1 <= values[i] <= 1000
• 1 <= W <= 1000