knapsackproblematikk

The knapsack problem, or knapsackproblematikk in some languages, is a classic combinatorial optimization problem. Given a set of items with associated weights and values, the task is to select a subset that maximizes total value without exceeding a weight capacity. The problem has numerous variants used in theory and applications.

In the canonical 0/1 version, each item is either taken or left behind. Formally, for items i = 1 to n with weight w_i and value v_i, choose x_i in {0,1} to maximize sum v_i x_i subject to sum w_i x_i ≤ W. In the fractional knapsack, x_i ∈ [0,1], allowing partial items.

Variants include the unbounded knapsack, where unlimited copies of each item may be taken; the multiple knapsack problem with several containers; and multidimensional knapsack, which imposes weight limits along several dimensions. Other forms add constraints such as precedences, conflicts, or stochastic weights.

Algorithms and complexity: the 0/1 problem admits a dynamic-programming solution running in pseudo-polynomial time O(nW). The fractional version is solvable greedily by sorting items by value-to-weight ratio. For large instances, approaches such as branch-and-bound, meet-in-the-middle, and approximation schemes (including FPTAS) are used.

Applications span resource allocation, budgeting, cargo loading, cutting stock, and portfolio optimization. The knapsack framework also serves as a testbed for algorithmic techniques in operations research and computer science.

Impact: The knapsack problem is a foundational problem in combinatorial optimization and integer programming. Its study has driven developments in dynamic programming, approximation algorithms, and complexity theory, illustrating how simple formulations can be computationally challenging.