ナップサック問題

knapsack.pl

#!/usr/bin/env perl

use strict;
use warnings;
use utf8;
use feature 'say';

use List::Util 'max';

chomp(my $input = <STDIN>);
my ($n, $w) = split(/ /, $input);
my ($val, $wei);
my $items = [];
for my $i (0..($n - 1)){
    chomp($input = <STDIN>);
    ($val, $weight) = split(/ /, $input);
    push(@$items, [$val, $weight]);
}
my $dp = [];
for my $j (0..$n){
    for my $k (0..$w){
        $dp->[$j]->[$k] = 0;
    }
}

for my $nums (1..$n){
    for my $weig (0..$w){
        if ($weig >= $items->[$nums - 1]->[1]){
            $dp->[$nums]->[$weig] = max($dp->[$nums - 1]->[$weig - $items->[$nums - 1]->[1]] + $items->[$nums - 1]->[0], $dp->[$nums - 1]->[$weig]);
        }
        else{
            $dp->[$nums]->[$weig] =  $dp->[$nums - 1]->[$weig];
        }
    }
}
say $dp->[$n]->[$w];