# NAME

Algorithm::Knap01DP - Solves the 0-1 Knapsack problem using the Dynamic Programming Technique

# SYNOPSIS

``````  use Algorithm::Knap01DP;

\$knap = Algorithm::Knap01DP->new( # constructor
capacity => 100, weights => [ 1..5 ], profits => [1..10]);
srand(7);
\$knap = Algorithm::Knap01DP->GenKnap(); # constructor: randomly generated problem

\$knap->Knap01DP(); # computes the DP tables
\$knap->solutions(); # computes all the solutions
\$knap->ShowResults(); # shows all the solutions``````

# DESCRIPTION

Solves the 0-1 Knapsack problem using the Dynamic Programming Technique. See an example of problem format

``````    \$ cat knapanderson.dat
6   # number of objects
30  # capacity
14  # weight object 0
14  # profit object 0
5   # etc.
5
2
2
11
11
3
3
8
8
``````

This corresponds to a problem with N=6, M=30 (objects, capacity) then the following consecutive pair of lines hold the weight and profit (in that order) of the different objects. A program illustrating the use of the module follows:

``````    \$ cat -n example.pl
1  use strict;
2  use Algorithm::Knap01DP;
3
4  die "Usage:\n\$0 knapsackfile\n" unless @ARGV;
6  \$knap->solutions();
7  \$knap->ShowResults();``````

The output is:

``````    \$ perl example.pl knapanderson.dat
Problem: knapanderson.dat
Number of Objects = 6 Capacity = 30
0 (14)  1 (5)   4 (3)   5 (8)   Used Capacity = 30
0 (14)  2 (2)   3 (11)  4 (3)   Used Capacity = 30
0 (14)  1 (5)   3 (11)  Used Capacity = 30
Profit = 30``````

The algorithm has complexity order M x N, being M the capacity and N the number of objects. Since M is usually much smaller than 2^N, the algorithm gives a efficient way to find all the solutions.

None by default.