NAME

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

SYNOPSIS

use Algorithm::Knap01DP;

$knap = Algorithm::Knap01DP->ReadKnap($file); # constructor: read from $file
$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

my @f = KnapP01DP($M, $w, $p);

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; 5 my $knap = Algorithm::Knap01DP->ReadKnap($ARGV[0]); 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

EXPORT

None by default.

SEE ALSO

Algorithm::Knapsack http://nereida.deioc.ull.es/~lhp/perlexamples/ (Spanish)

AUTHOR

Casiano Rodriguez Leon <casiano@ull.es>

COPYRIGHT AND LICENSE

Copyright (C) 2005 by Casiano Rodriguez Leon

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.4 or, at your option, any later version of Perl 5 you may have available.