Example
Input
knapsack([60,100,120],[10,20,30],50)
Output
220
Choose items with weights 20 and 30 for total value 100 + 120 = 220.
Full lesson preview
Solve 0/1 knapsack for maximum value
Implement the 0/1 knapsack DP to compute the maximum value achievable within a capacity constraint.
Python practice25 minDynamic ProgrammingAdvancedLast updated March 29, 2026
Problem statement
Given two lists values and weights of equal length n, and an integer capacity representing the maximum weight capacity of a knapsack, determine the maximum total value achievable by selecting a subset of the items such that the total weight does not exceed capacity. Each item can be chosen at most once (0/1 knapsack). Implement an efficient dynamic programming solution.
Task
Use dynamic programming (1D optimization or 2D table) to solve the 0/1 knapsack problem for maximum total value.
Examples
Input format
Three arguments: values (list of ints), weights (list of ints), capacity (int). values and weights have the same length.
Output format
An integer: the maximum total value achievable without exceeding the capacity.
Constraints
0 <= n <= 200. 0 <= weights[i] <= capacity <= 1000. values[i] are non-negative integers. Time complexity should be O(n * capacity) or better.
Samples
Sample 1
Input
knapsack([1,2,3],[1,1,1],2)
Output
5
Choose the two items with highest values (3 and 2) for total value 5.