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.

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

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

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

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

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.

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.

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.

You can go up one level to the DATASETS directory.


Last revised on 17 August 2014.