Skip to content

Knapsack problems

Catalogue of combinatorial problems · Catalogue (PDF)

  • Each item \(j\) has a profit \(p_j\) and a weight \(w_j\); a solution selects a subset, or a multiset, of the items whose weights satisfy one or more capacity constraints.

  • The objective is to maximize the total profit of the selected items; in the subset sum problem the total weight must be equal to a target value.

  • The members differ in the number of copies of each item, in the number of capacities and knapsacks, and in additional constraints on the selected items.

Problem Acronym Difference
0/1 knapsack problem KP The central problem of the family.
Subset sum problem SSP The SSP is solved as the KP with \(p_j = w_j\) for all \(j\in\Ioggetti\): the answer is yes if and only if the optimal value of this KP equals \(c\).
Bounded knapsack problem BKP The BKP reduces to the KP when \(b_j=1\) for every item, and to the UKP when every bound \(b_j\) is large enough not to be binding.
Unbounded knapsack problem UKP The UKP is the BKP with \(b_j = \hat b_j = \lfloor c/w_j \rfloor\): each item can be taken as many times as it fits.
Multidimensional knapsack problem MDKP The MDKP is the KP with \(k\) capacity constraints, one for each resource; with \(k=1\) it is the KP.
Multiple knapsack problem MKP The MKP is the KP with \(m\) knapsacks; every feasible solution of the MKP is feasible for the KP with capacity \(\sum_{k\in\mathscr{K}} c_k\), which gives a dual bound.
Multiple-choice knapsack problem MCKP The MCKP is the KP with the additional constraint that exactly one item of every class is selected, so an instance can be infeasible.
Knapsack problem with setups KPS The KPS is the KP in which selecting the first item of a class costs the setup \(f_h\) and consumes the setup weight \(s_h\); a class with no selected item costs nothing.