Data for the Subset Sum Problem

**SUBSET_SUM**
is a dataset directory which
contains some examples of data for the subset sum problem.

The subset sum problem is given a target value C and a set of N numbers W and seeks one or more subset of W that add up to exactly C, or if that is not possible, to come as close to C as possible without exceeding it.

An optimal solution is a subset W whose elements add up to C. An
optimal solution does not always exist. A *suboptimal solution* is
a subset W whose elements add up to a number Csub which is less than or
equal to C, such that there is no other subset whose sum is greater than
Csub but less than or equal to C. For any subset sum problem, there is
always at least one suboptimal solution.

A solution of the subset sum problem can be regarded as a binary number between 0 and 2^N-1, with the I-th binary digit indicating whether item I is included or excluded from the sum.

The subset problem problem is a special case of the 0-1 Knapsack problem, in which the profit of every item is equal to its weight.

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

BIN_PACKING, a dataset directory which contains examples of the bin packing problem, in which a number of objects are to be packed in the minimum possible number of uniform bins;

CHANGE_MAKING, a dataset directory which contains test data for the change making problem;

GENERALIZED_ASSIGNMENT, a dataset directory which contains test data for the generalized assignment problem;

KNAPSACK, a FORTRAN77 library which solves a variety of knapsack problems.

KNAPSACK_01, a dataset directory which contains test data for the 0/1 knapsack problem;

KNAPSACK_MULTIPLE, a dataset directory which contains test data for the multiple knapsack problem;

PARTITION_PROBLEM, a dataset directory which contains examples of the partition problem, in which a set of numbers is given, and it is desired to break the set into two subsets with equal sum.

SUBSET_SUM, a MATLAB library which seeks solutions of the subset sum problem.

**P01** is a set of N = 8 weights, for a target of 53. Three
solutions are given.

- p01_c.txt, the target value.
- p01_w.txt, the weights.
- p01_s.txt, three solutions, given as binary strings.

**P02** is a set of N = 10 weights, for a target of 5842.

- p02_c.txt, the target value.
- p02_w.txt, the weights.
- p02_s.txt, one solution, given as a binary string.

**P03** is a set of N = 21 weights, for a target of 2463098.

- p03_c.txt, the target value.
- p03_w.txt, the weights.
- p03_s.txt, one solution, given as a binary string.

**P04** is a set of N = 10 weights, for a target of 50.

- p04_c.txt, the target value.
- p04_w.txt, the weights.
- p04_s.txt, one solution, given as a binary string.

**P05** is a set of N = 9 weights, for a target of 100.

- p05_c.txt, the target value.
- p05_w.txt, the weights.
- p05_s.txt, one solution, given as a binary string.

**P06** is a set of N = 6 weights, for a target of 22.

- p06_c.txt, the target value.
- p06_w.txt, the weights.
- p06_s.txt, one solution, given as a binary string.

**P07** is a set of N = 10 weights, for a target of 50,
and comes from
Sam Loyd's Cyclopedia of Puzzles, 1914.

- p07_c.txt, the target value.
- p07_w.txt, the weights.
- p07_s.txt, one solution, given as a binary string.

You can go up one level to the DATASETS directory.