0/1 Knapsack

You are given n items, where the i-th item has weight weights[i] and value values[i], and an integer capacity representing the maximum weight your knapsack can hold. Each item can be taken at most once (you either take it whole or leave it — no fractional items). Return the maximum total value you can fit in the knapsack without exceeding capacity.

Example 1

Input: weights = [1, 3, 4, 5], values = [1, 4, 5, 7], capacity = 7
Output: 9
Explanation: Take items with weight 3 and weight 4 (value 4 + 5 = 9),
total weight 7.

Example 2

Input: weights = [2, 3], values = [4, 4], capacity = 4
Output: 4
Explanation: Only one item fits; either gives value 4.

Constraints

• 1 <= n <= 1000
• 1 <= weights[i], values[i] <= 1000
• 0 <= capacity <= 1000