Skip to content

Knapsack problems

Part 1 · Combinatorial optimization problems · Chapter 2 · Lecture notes, volume 1 (PDF) · Slides · Exercises: Knapsack problems · App: Brute force on the 0/1 knapsack problem

Prerequisites

Objectives

At the end of this chapter you will be able to:

  • state the definition of the 0/1 knapsack problem and of its variants, with instances and feasible solutions;

  • explain the assumptions on the data and why they can be made without loss of generality;

  • count the candidate solutions and the feasible solutions of a small instance;

  • find a feasible solution by hand and compute a simple combinatorial dual bound;

  • tell the variants apart: copies of the items, several resources, several knapsacks, classes of items.

2.1 Overview of the family

  • The knapsack problems share the same data: a set \(\mathscr{I} = \{1,2,\dots,n\}\) of \(n\) items, for each item \(j \in \mathscr{I}\) a weight \(w_j \in \Z_{\ge 1}\) and a profit \(p_j \in \Z_{\ge 1}\), and one or more knapsacks with a capacity in \(\Z_{\ge 1}\).

  • A solution decides which items are selected, or how many copies of each item: the total weight of the selected items must not exceed the capacity of the knapsack that receives them.

  • The objective is to maximize the total profit of the selected items.

A knapsack problem selects items of maximum total profit whose total weight respects the capacities. The members of the family differ in the number of copies of the items, in the number of capacities and of knapsacks, and in the classes into which the items are grouped.

  • The table lists the members of the family, with the section that defines each of them.
Problem Acronym Difference with respect to the KP Section
0/1 knapsack problem KP one copy of each item, one knapsack 2.2
subset sum problem SSP \(p_j = w_j\), total weight exactly equal to \(c\) 2.3
bounded knapsack problem BKP at most \(b_j\) copies of item \(j\) 2.4
unbounded knapsack problem UKP an unlimited number of copies of each item 2.5
multidimensional knapsack problem MDKP \(k\) capacities \(c_d\) and weights \(w_{dj}\) 2.6
multiple knapsack problem MKP \(m\) knapsacks with capacities \(c_k\) 2.7
multiple-choice knapsack problem MCKP classes \(\mathscr{J}_h\), exactly one item per class 2.8
knapsack problem with setups KPS classes \(\mathscr{J}_h\) with setup costs \(f_h\) and setup weights \(s_h\) 2.9

2.1.1 The variants at a glance

  • Each problem of the family is illustrated on a small instance, in its section of the table above and with the notation of that section.

  • The table lists, for these instances, the number of candidate solutions, the number of feasible solutions and the optimal value, computed by enumeration.

  • In the BKP and in the UKP a candidate solution is the vector of the numbers of copies of every item, so that identical copies are not counted twice.

  • The optimal solution is not always unique: the MKP, the MCKP and the KPS have several optimal solutions with the same value, and in the SSP three subsets reach the target.

Variant Candidate solutions Number Feasible Optimum Optimal solutions
KP subsets of \(6\) items \(64\) \(13\) \(15\) \(\{1,4\}\)
SSP subsets of \(6\) items \(64\) \(3\) yes \(\{6\}\), \(\{1,4\}\), \(\{2,3\}\)
BKP copies \(x_j \le b_j\) \(144\) \(18\) \(18\) two copies of item \(1\) and item \(5\)
UKP copies \(x_j \le \hat b_j\) \(320\) \(22\) \(24\) four copies of item \(1\)
MDKP subsets of \(4\) items \(16\) \(9\) \(14\) \(\{3,4\}\)
MKP each item in a knapsack or none \(243\) \(109\) \(30\) \((S_1,S_2) = (\{1,2\},\{4,5\})\), \((\{2,4\},\{1,5\})\), \((\{4,5\},\{1,2\})\)
MCKP one item per class \(8\) \(3\) \(17\) \(\{1,4,5\}\), \(\{2,3,5\}\)
KPS subsets of \(6\) items \(64\) \(40\) \(16\) \(\{1,2,3\}\), \(\{4,5,6\}\), \(\{1,2,3,6\}\)
  • In the MCKP only \(3\) of the \(8\) choices of one item per class fit in the knapsack: the feasibility condition among the assumptions of Section 2.8 is not a formality.

  • Overview

    Overview of the family · The variants at a glance

    Open

  • 2.2 The 0/1 knapsack problem

    Counting the solutions, a first solution and a simple bound

    Open

  • 2.3 The subset sum problem

    Open

  • 2.4 The bounded knapsack problem

    Open

  • 2.5 The unbounded knapsack problem

    Open

  • 2.6 The multidimensional knapsack problem

    Open

  • 2.7 The multiple knapsack problem

    Open

  • 2.8 The multiple-choice knapsack problem

    Open

  • 2.9 The knapsack problem with setups

    Remarks · Typical mistakes · In summary

    Open

Next: 2.2 The 0/1 knapsack problem

Exercises on this chapter: Knapsack problems

In depth: what the course does on this problem

In the interactive lab: Brute force on the 0/1 knapsack problem.