Knapsack Problem

The knapsack problem is one of the most fundamental problems in combinatorial optimization: given a set of items, each with a weight and a value, determine the subset to include in a collection so that the total weight does not exceed a given limit and the total value is maximized. The name is literal — it describes a hiker choosing what to pack — but the problem is universal: capital budgeting, resource allocation, cargo loading, and investment selection all reduce to knapsack structure.\n\nThe problem has a deceptive simplicity. A greedy strategy — pack the most valuable items first, or the most value-dense items first — fails because it ignores weight interactions. The optimal solution may include a low-value, low-weight item that makes room for a high-value, high-weight item the greedy approach would exclude. This failure of local reasoning is the signature of discrete optimization: the whole is not approximable by its best parts.\n\nIn its basic form, the knapsack problem is NP-hard. But it is also pseudo-polynomial: solvable in time proportional to the capacity of the knapsack, which is polynomial in the numeric value of the capacity but exponential in its bit-length. This liminal status — hard in the formal sense, tractable in the practical sense for moderate capacities — makes the knapsack problem a test case for the relationship between theoretical complexity and real-world difficulty.\n\nThe dynamic programming solution builds a table of optimal values for every sub-capacity, computing each entry from previously solved smaller problems. The structure is a classic instance of optimal substructure: the solution for capacity W depends on solutions for capacities less than W. This makes the problem one of the most accessible introductions to both dynamic programming and the boundary between tractable and intractable.\n\nThe knapsack problem is a parable about constraints. It asks not what you want, but what you can afford to carry — and the answer is never the obvious one.\n\n\n\n