0/1 Knapsack

Given n items with weights and values, and a knapsack capacity, return the maximum total value you can achieve by picking each item at most once. This is the classic 0/1 knapsack formulation and the base of many partition-style DP problems.

Input Format

weights = item weights, values = item values, capacity = knapsack capacity

Output Format

maximum total value without exceeding capacity

Constraints

• 1 <= n <= 2000; 1 <= weights[i], values[i] <= 10^4; 0 <= capacity <= 10^4

Examples

weights = [1,3,4,5]
values = [1,4,5,7]
capacity = 7

9

weights = [2,3,4,5]
values = [3,4,5,6]
capacity = 5

7