PARTITION_PROBLEM
Data for the Partition Problem

PARTITION_PROBLEM is a dataset directory which contains some examples of data for the partition problem.

The partition problem is given a set of N numbers W, and it is desired to separate these numbers into two subsets W1 and W2 so that the sums of the numbers in each subset are equal.

The partition problem is a special case of the subset sum problem, in which the target sum is one half the sum of the entire set W.

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 dataset directory which contains examples of the subset sum problem, in which a set of numbers is given, and is desired to find at least one subset that sums to a given target value.

Reference:

1. Alexander Dewdney,
   The Turing Omnibus,
   Freeman, 1989,
   ISBN13: 9780716781547,
   LC: QA76.D45.
2. Brian Hayes,
   The Easiest Hard Problem,
   American Scientist,
   Volume 90, Number 2, March-April 2002, pages 113-117.
3. Silvano Martello, Paolo Toth,
   Knapsack Problems: Algorithms and Computer Implementations,
   Wiley, 1990,
   ISBN: 0-471-92420-2,
   LC: QA267.7.M37.

Datasets:

P01 is a set of N = 10 weights. There are 23 distinct pairs of partitions that sum to 27.

• p01_w.txt, the weights.
• p01_s.txt, a solution.

P02 is a set of N = 10 weights. There is only one pair of partitions, which sum to 2640.

• p02_w.txt, the weights.
• p02_s.txt, the solution.

P03 is a set of N = 9 weights. There is only one pair of partitions which sum to 1,419.

• p03_w.txt, the weights.
• p03_s.txt, the solution.

P04 is a set of N = 5 weights. There is a least one pair of partitions which sum to 32.

• p04_w.txt, the weights.
• p04_s.txt, a solution.

P05 is a set of N = 9 weights. There is a least one pair of partitions which sum to 11.

• p05_w.txt, the weights.
• p05_s.txt, a solution.

You can go up one level to the DATASETS directory.