0/1 Knapsack

Problem

Given item weights, item values and a capacity, return the maximum total value achievable without exceeding the capacity, where each item may be taken at most once.

Use one-dimensional dynamic programming over capacities, processing each item and updating capacities from high to low so no item is reused. Weights, values and capacity are non-negative integers.

Hint

Iterate capacities downward so each item can be chosen at most once.

Test cases

case 1

in: [[1,3,4,5],[1,4,5,7],7]

expected: 9

case 2

in: [[2,2,3],[3,4,5],4]

expected: 7

case 3

in: [[],[],0]

expected: 0

case 4

in: [[5],[10],4]

expected: 0

case 5

in: [[1,2,3],[6,10,12],5]

expected: 22

Starter codePython

def knapsack(weights, values, capacity):
    # Your code here
    pass

5 test cases · run your code against them in the editor