view release on metacpan or  search on metacpan

lib/Algorithm/Knap01DP.pm  view on Meta::CPAN

  print "Number of Objects = $self->{numobjects} Capacity = $self->{capacity}\n";
  for (@sol) {
    my @s = @{$_->{sol}};

    $i = 1;
    $w = 0;
    for $x (@s) {
      print "$x ($self->{weights}[$x])\t";
      $w += $self->{weights}[$x];
      print "\n" if ($i % $width) == 0;
      $i++;
    }
    print "Used Capacity = $w\n";
  }
  print "Profit = $self->{tableval}[-1][-1]\n";
}

1;
__END__

=head1 NAME

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

=head1 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

=head1 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

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.

=head2 EXPORT

None by default.

=head1 SEE ALSO

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

=head1 AUTHOR

Casiano Rodriguez Leon E<lt>casiano@ull.esE<gt>

=head1 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.


=cut