SUBSET_SUM
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.

Licensing:

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

Related Data and Programs:

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.

Datasets:

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.