Algorithm::KnapsackAlgorithm::Knapsack is a brute-force algorithm for the knapsack problem. | |
Download |
Algorithm::Knapsack Ranking & Summary
Advertisement
- License:
- Perl Artistic License
- Price:
- FREE
- Publisher Name:
- Alexander Anderson
- Publisher web site:
- http://search.cpan.org/~andale/Algorithm-Knapsack-0.02/lib/Algorithm/Knapsack.pm
Algorithm::Knapsack Tags
Algorithm::Knapsack Description
Algorithm::Knapsack is a brute-force algorithm for the knapsack problem. Algorithm::Knapsack is a brute-force algorithm for the knapsack problem.SYNOPSIS use Algorithm::Knapsack; my $knapsack = Algorithm::Knapsack->new( capacity => $capacity, weights => @weights, ); $knapsack->compute(); foreach my $solution ($knapsack->solutions()) { foreach my $index (@{$solution}) { # do something with $weights } }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.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.METHODSnew my $knapsack = Algorithm::Knapsack->new( capacity => $capacity, weights => @weights, );Creates a new Algorith::Knapsack object. Value of $capacity is a positive integer and @weights is a reference to an array of positive integers, each of which is less than $capacity.compute $knapsack->compute();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.solutions my @solutions = $knapsack->solutions();Returns a list of solutions. Each solution is a reference to an array of indexes to @weights. Requirements: · Perl
Algorithm::Knapsack Related Software