.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.29)
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" Set up some character translations and predefined strings.  \*(-- will
.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
.\" double quote, and \*(R" will give a right double quote.  \*(C+ will
.\" give a nicer C++.  Capital omega is used to do unbreakable dashes and
.\" therefore won't be available.  \*(C` and \*(C' expand to `' in nroff,
.\" nothing in troff, for use with C<>.
.tr \(*W-
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
.ie n \{\
.    ds -- \(*W-
.    ds PI pi
.    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
.    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
.    ds L" ""
.    ds R" ""
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds -- \|\(em\|
.    ds PI \(*p
.    ds L" ``
.    ds R" ''
.    ds C`
.    ds C'
'br\}
.\"
.\" Escape single quotes in literal strings from groff's Unicode transform.
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\"
.\" If the F register is turned on, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.\"
.\" Avoid warning from groff about undefined register 'F'.
.de IX
..
.nr rF 0
.if \n(.g .if rF .nr rF 1
.if (\n(rF:(\n(.g==0)) \{
.    if \nF \{
.        de IX
.        tm Index:\\$1\t\\n%\t"\\$2"
..
.        if !\nF==2 \{
.            nr % 0
.            nr F 2
.        \}
.    \}
.\}
.rr rF
.\" ========================================================================
.\"
.IX Title "Algorithm::Knapsack 3"
.TH Algorithm::Knapsack 3 "2004-10-23" "perl v5.22.0" "User Contributed Perl Documentation"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.if n .ad l
.nh
.SH "NAME"
Algorithm::Knapsack \- brute\-force algorithm for the knapsack problem
.SH "SYNOPSIS"
.IX Header "SYNOPSIS"
.Vb 1
\&    use Algorithm::Knapsack;
\&
\&    my $knapsack = Algorithm::Knapsack\->new(
\&        capacity => $capacity,
\&        weights  => \e@weights,
\&    );
\&
\&    $knapsack\->compute();
\&
\&    foreach my $solution ($knapsack\->solutions()) {
\&        foreach my $index (@{$solution}) {
\&            # do something with $weights[$index]
\&        }
\&    }
.Ve
.SH "DESCRIPTION"
.IX Header "DESCRIPTION"
The knapsack problem asks, given a set of items of various weights, find a
subset or subsets of items such that their total weight is no larger than
some given capacity but as large as possible.
.PP
This module solves a special case of the 0\-1 knapsack problem when the
value of each item is equal to its weight. Capacity and weights are
restricted to positive integers.
.SH "METHODS"
.IX Header "METHODS"
.IP "\fBnew\fR" 7
.IX Item "new"
.Vb 4
\&    my $knapsack = Algorithm::Knapsack\->new(
\&        capacity => $capacity,
\&        weights  => \e@weights,
\&    );
.Ve
.Sp
Creates a new Algorith::Knapsack object. Value of \f(CW$capacity\fR is a
positive integer and \e@weights is a reference to an array of positive
integers, each of which is less than \f(CW$capacity\fR.
.IP "\fBcompute\fR" 7
.IX Item "compute"
.Vb 1
\&    $knapsack\->compute();
.Ve
.Sp
Iterates over all possible combinations of weights to solve the knapsack
problem. Note that the time to solve the problem grows exponentially with
respect to the number of items (weights) to choose from.
.IP "\fBsolutions\fR" 7
.IX Item "solutions"
.Vb 1
\&    my @solutions = $knapsack\->solutions();
.Ve
.Sp
Returns a list of solutions. Each solution is a reference to an array of
indexes to \f(CW@weights\fR.
.SH "EXAMPLES"
.IX Header "EXAMPLES"
The following program solves the knapsack problem for a list of weights
(14, 5, 2, 11, 3, 8) and capacity 30.
.PP
.Vb 10
\&    use Algorithm::Knapsack;
\&    my @weights = (14, 5, 2, 11, 3, 8);
\&    my $knapsack = Algorithm::Knapsack\->new(
\&        capacity => 30,
\&        weights  => \e@weights,
\&    );
\&    $knapsack\->compute();
\&    foreach my $solution ($knapsack\->solutions()) {
\&        print join(\*(Aq,\*(Aq, map { $weights[$_] } @{$solution}), "\en";
\&    }
.Ve
.PP
The output from the above program is:
.PP
.Vb 3
\&    14,5,11
\&    14,5,3,8
\&    14,2,11,3
.Ve
.SH "AUTHOR"
.IX Header "AUTHOR"
Alexander Anderson <a.anderson@utoronto.ca>
.SH "COPYRIGHT"
.IX Header "COPYRIGHT"
.Vb 3
\& Copyright (c) 2004 Alexander Anderson. All rights reserved.
\& This program is free software; you can redistribute it and/or
\& modify it under the same terms as Perl itself.
.Ve