0/1 Knapsack

You are given arrays weights and values, and an integer capacity. Each item can be taken at most once. Return the maximum total value that fits within the capacity.

Function signature

func Knapsack01(weights []int, values []int, capacity int) int

Example

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

Constraints

• 0 <= len(weights) == len(values) <= 200
• 0 <= capacity <= 20_000
• 1 <= weights[i] <= 1_000
• 0 <= values[i] <= 10_000

Notes

• Use 1D DP and iterate capacity backwards for 0/1 knapsack.