knapsackprobleem

The knapsackprobleem, known in English as the knapsack problem, is a classic optimization problem in combinatorial optimization. Given a set of items i with weights w_i and values v_i, and a knapsack with capacity W, the task is to select a subset of items whose total weight does not exceed W and whose total value is maximized. In Dutch literature the term knapsackprobleem is commonly used to refer to this problem.

The problem has several variants. In the 0/1 knapsack problem, each item can be chosen at most once. In the fractional knapsack problem, items may be split, so parts of an item can be taken; this version is efficiently solvable by a greedy algorithm. The unbounded (or infinite) knapsack allows multiple copies of each item.

Complexity and methods: The 0/1 version is NP-hard, and the decision version is NP-complete. A dynamic programming solution runs in O(nW) time and space, providing a pseudo-polynomial algorithm. The fractional version is solvable in polynomial time by sorting items by value-to-weight ratio and filling the knapsack greedily. Other approaches include branch-and-bound, meet-in-the-middle, and approximation schemes such as a fully polynomial-time approximation scheme (FPTAS) for the 0/1 version.

Applications of the knapsackprobleem include resource allocation, budgeting, project selection, cargo loading, and portfolio optimization. It serves as a standard benchmark in optimization and algorithm design, illustrating the trade-off between computation and exactness across problem variants.

Historically, the problem has been studied since the mid-20th century and remains a fundamental example in operations research and computer science. Notation typically uses p_i or v_i for value and w_i for weight, with a capacity constraint W.