Subset sum problem (SSP)

Catalogue of combinatorial problems · Knapsack problems · Catalogue (PDF)

Definition 1: Subset sum problem

Given:

1. a target value \(c \in \Z_{\ge 1}\),

2. a set \(\mathscr{I} = \{1,2,\dots,n\}\) of \(n\) items,

3. for each item \(j \in \mathscr{I}\), a weight \(w_j \in \Z_{\ge 1}\),

the Subset Sum Problem (SSP) asks whether there exists a subset of items whose total weight is exactly equal to the target value \(c\).

Assumptions

• We make the following assumptions:

  1. The total weight of all items is at least the target value (otherwise, no feasible subset can exist). Formally:

     \[ \sum_{j \in \mathscr{I}} w_j \ge c \]

  2. Each item weight is not larger than the target value (otherwise, it cannot belong to any feasible subset). Formally:

     \[ w_j \le c,~~~~ \forall j \in \mathscr{I} \]

What the course does on this problem

Technique	Where
Definition	Ch. 2 «Knapsack problems»
Formulations	Ch. 9 «Formulations of knapsack problems»
Dynamic programming	Ch. 16 «Principles of dynamic programming»; Ch. 20 «DP for the subset sum problem»
Exercises	Exercise 2.2; Exercise 9.6; Exercise 16.2; Ch. 20 (5 exercises)