codejump
HardPro challengePython

Dynamic Programming — 0/1 Knapsack

PythonDynamic ProgrammingAlgorithms

Given weights, values (both lists of integers) and a capacity, return the maximum total value you can fit in a knapsack of that capacity. Each item can be taken at most once.

Examples

  • solve([1,3,4,5], [1,4,5,7], 7) → 9 (items with weight 3+4, value 4+5)
  • solve([2,3,4,5], [3,4,5,6], 5) → 7 (items weight 2+3)
  • solve([1], [10], 0) → 0

Constraints

  • Use bottom-up 2-D DP.
  • 1 ≤ n ≤ 100, 0 ≤ capacity ≤ 1000.

Sample tests

Test #1Capacity 5
Input: [[2,3,4,5],[3,4,5,6],5]
Output: 7
Test #2Classic example — max value 9
Input: [[1,3,4,5],[1,4,5,7],7]
Output: 9
Test #3Zero capacity
Input: [[1],[10],0]
Output: 0
← All challenges