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

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

　Algorithm::Knap01DP - 動的計画法で 0-1 ナップサック問題を解く

use Algorithm::Knap01DP;

$knap = Algorithm::Knap01DP->ReadKnap($file); # コンストラクタ：ファイル $file から読み込む
$knap = Algorithm::Knap01DP->new( # コンストラクタ
            capacity => 100, weights => [ 1..5 ], profits => [1..10]);
srand(7);
$knap = Algorithm::Knap01DP->GenKnap(); # コンストラクタ：乱数で生成

$knap->Knap01DP();    # 動的計画表を計算
$knap->solutions();   # 全ての解を計算
$knap->ShowResults(); # 全ての解を表示

説明

　動的計画法で 0-1 ナップサック問題を解く。問題のフォーマットの例を見よ。

$ cat knapanderson.dat
6   # オブジェクトの数
30  # 容量
14  # オブジェクト 0 の重み（weight）
14  # オブジェクト 0 の利益（profit）
5   # その他
5
2
2
11
11
3
3
8
8

　これは N = 6, M = 30 （オブジェクト，容量）の問題に対応している。異なるオブジェクトの（その順に）重みと利益が順に並べられている。以下にモジュールの使用方法を示す。

$ 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();

　出力は以下の通り。

$ 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

　アルゴリズムは容量を M 、オブジェクトの数を N として、M x N の計算量である。Since M は通常 2^N よりかなり小さいのでアルゴリズムは全ての解を探索するのに有効な方法である。

エクスポート

　デフォルトではなし。

参考資料

　Algorithm::Knapsack http://nereida.deioc.ull.es/~lhp/perlexamples/ （スペイン語）

著者

　Casiano Rodriguez Leon, <casiano@ull.es>

著作権とライセンス

　本ライブラリはフリーソフトウェアであり、 Perl 本体と同等の条件で修正／再配布してもよい。Perl 5.8.4 またはユーザの選択で Perl5 のこれ以降のバージョンでもよい。

Updated : 2007/01/13