0/1 Knapsack Dynamic Programming

Background

The knapsack problem is a classic optimization problem in combinatorics, resource allocation, and cryptography.

Problem

Write a function that takes items with weights and values, and a capacity, returning the maximum value achievable without exceeding the capacity.

Input

An array of items (each with weight and value) and a capacity number.

Output

The maximum total value achievable within the weight capacity.

Sample tests

Input: items=[{w:2,v:3},{w:3,v:4},{w:4,v:5}], capacity=5

Expected: 7

Your solution

Learning objective

Master dynamic programming with space optimization and understand the 0/1 knapsack recurrence.