Location : Home > Languages > Perl > Package Title : Algorithm::Knapsack

名称

　Algorithm::Knapsack - ナップサック問題を総当り法で解く

概要

use Algorithm::Knapsack;

my $knapsack = Algorithm::Knapsack->new(
   capacity => $capacity,
   weights  => \@weights,
);

$knapsack->compute();

foreach my $solution ($knapsack->solutions()) {
   foreach my $index (@{$solution}) {
      # $weights[$index] を使った処理
   }
}

説明

　ナップサック問題とは、所与の様々な重みのものの集合から、ある容量以下にする（ただしできるだけ大きく）部分集合を取り出すものである。
　本モジュールは、値がそれぞれの重みに等しい 0-1ナップサック問題を扱う。容量と重みは正の整数に限られている。

メソッド

new

my $knapsack = Algorithm::Knapsack->new(
   capacity => $capacity,
   weights  => \@weights,
);

　新しい Algorith::Knapsack オブジェクトを生成する。$capacity の値は正の整数であり、 \@weights は $capacity よりも小さい、正の整数の配列への参照である。

compute

$knapsack->compute();

　ナップサック問題を解くために重みの可能な全ての組み合わせを試す。問題を解くために必要な時間は選ばれるものの数につれ指数的に大きくなることに注意すること。

solutions

my @solutions = $knapsack->solutions();

　解のリストを返す。それぞれの解は @weights のインデクスの配列への参照である。

使用例

　下のプログラムは、重みのリストが（14, 5, 2, 11, 3, 8）であり容量（capacity）が30であるようなナップサック問題を記す。

use Algorithm::Knapsack;
my @weights = (14, 5, 2, 11, 3, 8);
my $knapsack = Algorithm::Knapsack->new(
    capacity => 30,
    weights  => \@weights,
);
$knapsack->compute();
foreach my $solution ($knapsack->solutions()) {
    print join(',', map { $weights[$_] } @{$solution}), "\n";
}

　上の問題に対する出力は

14,5,11
14,5,3,8
14,2,11,3

著者

　Alexander Anderson, <a.anderson@utoronto.ca>

著作権

　Copyright (C) 2004 Alexander Anderson. All Rights Reserved.
　本プログラムはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布することができる。

Updated : 2006/07/26