Knapsack Maximum Value

You are given two integer arrays weights and values of equal length n, and an integer capacity. Item i has weight weights[i] and value values[i].

Choose a subset of the items such that the total weight of the chosen items does not exceed capacity. Each item may be chosen at most once, and items cannot be chosen partially.

Return the maximum total value of any valid subset. If no item fits, the answer is 0 (the empty subset).

Examples

Example 1

Input: weights = [2,3,1], values = [20,30,15], capacity = 4
Output: 45
Explanation: Choose items 1 and 2 (weights 3 + 1 = 4, values 30 + 15 = 45). No other valid subset has a larger total value.

Example 2

Input: weights = [4,2,3], values = [50,20,40], capacity = 5
Output: 60
Explanation: Choose items 1 and 2 (weights 2 + 3 = 5, values 20 + 40 = 60). Item 0 alone is worth 50, which is less.

Example 3

Input: weights = [5,6,7], values = [10,20,30], capacity = 4
Output: 0
Explanation: No single item fits within the capacity, so the empty subset is optimal.