2.3 The subset sum problem¶
Part 1 · Combinatorial optimization problems · Chapter 2 · Chapter 2: Knapsack problems · Lecture notes, volume 1 (PDF) · Slides · Exercises: Knapsack problems · App: Brute force on the 0/1 knapsack problem
Definition 2.3: Subset Sum Problem
Given:
-
a target value \(c \in \Z_{\ge 1}\),
-
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}\),
the Subset Sum Problem (SSP) asks whether there exists a subset of items whose total weight is exactly equal to the target value \(c\).
-
An SSP instance is specified by:
-
two integer numbers:
-
the number of items \(n \in \Z_{\ge 1}\),
-
the target value \(c \in \Z_{\ge 1}\),
-
-
one vector of integer numbers of length \(n\):
- \(\vet{w} \in \Z_{\ge 1}^n\), containing the item weights.
-
-
An SSP feasible solution is a subset of items
\[ S \subseteq \mathscr{I} \]such that the total weight of the selected items is exactly equal to the target value, namely
\[ \sum_{j\in S} w_j = c . \]Accordingly, the SSP can be equivalently stated as the problem of selecting a subset of items whose total weight matches the target value exactly.
Given an SSP instance, the SSP can be formally stated as:
\[\begin{equation*} \label{SSP} \text{find } S \subseteq \mathscr{I} \quad \text{such that} \quad \sum_{j \in S} w_j = c . \tag{2.2} \end{equation*}\]
Example 2.2: SSP instance
We consider a target value \(c = 9\) and a set \(\mathscr{I} = \{1,2,3,4,5,6\}\) of \(6\) items (\(n = 6\)), with the following weights:
| Items | \(j = 1\) | \(j = 2\) | \(j = 3\) | \(j = 4\) | \(j = 5\) | \(j = 6\) | |
|---|---|---|---|---|---|---|---|
| Weights | \(w_j\) | \(2\) | \(3\) | \(6\) | \(7\) | \(5\) | \(9\) |
For instance, the subset \(S=\{1,4\}\) is feasible since \(w_1+w_4=2+7=9\). Also, the subset \(S=\{6\}\) is feasible since \(w_6=9\). The drawing shows the three subsets whose weights fill the box of length \(c=9\) exactly: \(\{1,4\}\), \(\{6\}\) and \(\{2,3\}\).
-
The SSP is not an optimization problem, since its answer is either yes or no. However, it can be solved by using an optimization problem.
-
An SSP instance can be solved as a KP instance by setting the profit of each item equal to its weight, namely
\[ p_j = w_j, \qquad \forall j\in \mathscr{I}. \]In this case, we solve the following KP:
\[\begin{equation*} \tilde{S}\in \arg\max_{S \subseteq \mathscr{I}} \left\{~~ \sum_{j \in S} w_j \;\;:\;\; \sum_{j \in S} w_j \le c ~~\right\}. \end{equation*}\]If \(\sum_{j\in \tilde{S}} w_j = c\), then the answer to the SSP is yes; otherwise, if \(\sum_{j\in \tilde{S}} w_j < c\), the answer is no.
2.3.1 Assumptions¶
-
We make the following assumptions:
-
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 \] -
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} \]
-