0-1 knapsack problem via dynamic programming

knapsack.py

import numpy as np
import functools

def knapsack(capacity, items):
    n = len(items)
    
    A = np.zeros((n, capacity))
    
    for i in range(n):
        value, weight = items[i]
        for x in range(capacity):
            if weight > x:
                A[i, x] = A[i-1, x]
                continue
                
            A[i, x] = max(A[i-1, x], A[i-1, x - weight] + value)
    
    return A[-1, -1]

def knapsack_vectorized(capacity, items):
    n = len(items)
    
    A = np.zeros((n, capacity))
    
    for i in range(n):
        value, weight = items[i]
        A[i, :weight] = A[i-1, :weight]
        A[i, weight:] = np.fmax(A[i-1, weight:], A[i-1, np.arange(weight, capacity) - weight] + value)
                
    return A[-1, -1]

@functools.lru_cache(maxsize=None)
def recursive_knapsack(capacity, items):
    
    if capacity == 0:
        return 0
    
    if len(items) == 0:
        return 0
    
    if capacity < items[-1][1]:
        return recursive_knapsack(capacity, items[:-1])
    
    # can optimize this further by not providing copies of sub-arrays
    return max(recursive_knapsack(capacity, items[:-1]),
              recursive_knapsack(capacity - items[-1][1], items[:-1]) + items[-1][0])