Binary Subset Sum

Given a set of integers \( S = \{a_1, a_2, \dots, a_n\} \) and a target sum \( T \), the goal is to find a subset \( S' \subseteq S \) such that the sum of the elements in \( S' \) is as close as possible to \( T \).

The subset \( S' \) is represented by a binary string \( x = (x_1, x_2, \dots, x_n) \), where: \( x_i = \begin{cases} 1 & \text{if } a_i \in S' \\ 0 & \text{if } a_i \notin S' \end{cases} \)

The objective function is to minimize the absolute difference between the sum of the selected elements and the target \( T \): \( f(x) = \left| \sum_{i=1}^{n} x_i a_i - T \right| \)

Example: Given the set \( S = \{3, 34, 4, 12, 5, 2\} \) and a target sum \( T = 9 \), the optimal subset \( S' = \{4, 5\} \) results in a sum of 9.