Knapsack Problem

Optimization · Axiom Academy

Maximize value subject to capacity constraints: from exact solutions to practical approximations Given a set of items, each with a weight and value, determine which items to include in a knapsack to maximize total value without exceeding the weight capacity. n items, each with weight w i and value v i Example: Items with (weight, value): (2, 3), (3, 4), (4, 8), (5, 10). Capacity = 8. 2. 0-1 Knapsack IP Formulation The 0-1 knapsack problem can be formulated as an Integer Program where each item is either included (x i = 1) or excluded (x i = 0). 3. Dynamic Programming Solution Dynamic programming provides an exact solution by building a table where DP[i][w] represents the maximum value achievable using the first i items with capacity w. 4. Greedy Approximation Algorithm A fast heuristic sorts items by value-to-weight ratio and greedily selects items in descending order until capacity is reached. 5. Exact vs Approximate Solutions Understanding the trade-offs between exact and approximate solutions helps choose the right approach for different scenarios.

This is the written version of the interactive lesson above. See the full Optimization course.