>>629 Perl5
use List::Util qw{max};
$W = 20;
$n = @wv = ([3, 5],[5, 6],[6, 3],[3, 5],[5, 9],[2, 1],[7, 5],[4, 6],[8, 3]);
@w = map{$$_[0]} @wv;
@v = map{$$_[1]} @wv;
$wt[$n][$_] = 0 for 0..$W;
for ($i = $n - 1; $i >= 0; $i--) {
　for $j (0..$W) {
　　$ws = $wt[$i + 1][$j];
　　$ws = max($wt[$i + 1][$j - $w[$i]] + $v[$i], $ws) if $j >= $w[$i];
　　$wt[$i][$j] = $ws;
　}
}
print "価値合計最大: $wt[0][$W]\n";
$j = $W;
for $i (0..$n-1) {
　$ws = $wt[$i][$j];
　if ($wt[$i + 1][$j] != $ws) {
　　print "[$w[$i], $v[$i]] ";
　　$ws -= $v[$i];
　　for (; 0 <= $j; $j--) { last if $wt[$i + 1][$j] == $ws; }
　}
}

$ perl 16_629_nsp_dp.pl
価値合計最大: 31
[3, 5]
[5, 6]
[3, 5]
[5, 9]
[4, 6]