KNAPSACK_01
Data for the 01 Knapsack Problem

KNAPSACK_01 is a dataset directory which contains some examples of data for 01 Knapsack problems.

In the 01 Knapsack problem, we are given a knapsack of fixed capacity C. We are also given a list of N objects, each having a weight W(I) and profit P(I). We can put any subset of the objects into the knapsack, as long as the total weight of our selection does not exceed C. We desire to maximize our total profit, which is the sum of the profits of each object we put into the knapsack.

Thus, a solution of the 01 Knapsack problem is a subset S of the N objects for which the weight sum is less than or equal to C, and which maximizes the total profit.

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_MULTIPLE, a dataset directory which contains test data for the multiple knapsack problem;

LAU_NP, a FORTRAN90 library which implements heuristic algorithms for various NP-hard combinatorial problems.

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. Donald Kreher, Douglas Simpson,
   Combinatorial Algorithms,
   CRC Press, 1998,
   ISBN: 0-8493-3988-X,
   LC: QA164.K73.
2. 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 10 weights and profits for a knapsack of capacity 165.

• p01_c.txt, the knapsack capacity.
• p01_w.txt, the weights of the objects.
• p01_p.txt, the profits of each object.
• p01_s.txt, the optimal selection of weights.

P02 is a set of 5 weights and profits for a knapsack of capacity 26.

• p02_c.txt, the knapsack capacity.
• p02_w.txt, the weights of the objects.
• p02_p.txt, the profits of each object.
• p02_s.txt, the optimal selection of weights.

P03 is a set of 6 weights and profits for a knapsack of capacity 190.

• p03_c.txt, the knapsack capacity.
• p03_w.txt, the weights of the objects.
• p03_p.txt, the profits of each object.
• p03_s.txt, the optimal selection of weights.

P04 is a set of 7 weights and profits for a knapsack of capacity 50.

• p04_c.txt, the knapsack capacity.
• p04_w.txt, the weights of the objects.
• p04_p.txt, the profits of each object.
• p04_s.txt, the optimal selection of weights.

P05 is a set of 8 weights and profits for a knapsack of capacity 104.

• p05_c.txt, the knapsack capacity.
• p05_w.txt, the weights of the objects.
• p05_p.txt, the profits of each object.
• p05_s.txt, the optimal selection of weights.

P06 is a set of 7 weights and profits for a knapsack of capacity 170. The knapsack can be packed to an optimal weight of 169.

• p06_c.txt, the knapsack capacity.
• p06_w.txt, the weights of the objects.
• p06_p.txt, the profits of each object.
• p06_s.txt, the optimal selection of weights.

P07 is a set of 15 weights and profits for a knapsack of capacity 750, from Kreher and Stinson, with an optimal profit of 1458.

• p07_c.txt, the knapsack capacity.
• p07_w.txt, the weights of the objects.
• p07_p.txt, the profits of each object.
• p07_s.txt, the optimal selection of weights.

P08 is a set of 24 weights and profits for a knapsack of capacity 6404180, from Kreher and Stinson, with an optimal profit of 13549094.

• p08_c.txt, the knapsack capacity.
• p08_w.txt, the weights of the objects.
• p08_p.txt, the profits of each object.
• p08_s.txt, the optimal selection of weights.

You can go up one level to the DATASETS directory.