Knapsackproblemet

Knapsackproblemet is a classical problem in combinatorial optimization. In its standard form, a set of n items each has a weight w_i and a value v_i. A knapsack with capacity W can carry at most total weight W. The task is to select a subset of items to maximize total value without exceeding capacity. Mathematically, one chooses x_i in {0,1} to maximize sum v_i x_i subject to sum w_i x_i ≤ W.

Its variants include the 0/1 knapsack problem (each item can be chosen at most once), the fractional or continuous knapsack problem (items can be split, and the problem is solvable by a greedy approach using value-to-weight ratio), the unbounded knapsack (unlimited copies of each item), and multidimensional or multiple-knapsack forms (multiple constraints or bins).

Computationally, the 0/1 knapsack problem is NP-hard; the corresponding decision version is NP-complete. However, it admits a pseudo-polynomial time dynamic programming solution with time and space complexity O(nW). For the fractional variant, a greedy algorithm yields an optimal solution and informs many approximation and heuristic methods. In practice, additional techniques such as branch-and-bound and meet-in-the-middle are used for large or specially structured instances.

Applications of Knapsackproblemet include budgeting and resource allocation, cargo loading, project selection, and various logistics optimizations. It is a standard benchmark in theoretical computer science and operations research and serves to illustrate the trade-offs between exact methods and approximations in combinatorial optimization.