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.

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

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

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

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

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

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

You can go up one level to the DATASETS directory.


Last revised on 31 December 2013.