Algorithm::Knap01DP - Solves the 0-1 Knapsack problem using the Dynamic Programming Technique
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
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
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.
Algorithm::Knapsack http://nereida.deioc.ull.es/~lhp/perlexamples/ (Spanish)
Casiano Rodriguez Leon <casiano@ull.es>
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.
To install Algorithm::Knap01DP, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Algorithm::Knap01DP
CPAN shell
perl -MCPAN -e shell install Algorithm::Knap01DP
For more information on module installation, please visit the detailed CPAN module installation guide.