問題文
joishinoお姉ちゃんの次の仕事は、書類の書き換えである。
書類はN個あり、それぞれに、重要度と、書き換えるのにかかる時間が決まっている。
joishinoお姉ちゃんはどうしても定時に帰りたいので、あと作業できる時間はMしかない。
そこでjoishinoお姉ちゃんは、時間内に書き換える書類の重要度の合計の最大化したいと思い、その最大値を求めるプログラムを作ることにした。
入力
入力は以下の形式で標準入力から与えられる。
N M V1 T1 V2 T2 : VN TN
- 1行目には、書類の個数を表す整数N(1≦N≦500)と残っている時間M(1≦M≦500)が書かれている。
- 続くN行のうちi行目には、i番目の書類の重要度Vi(1≦Vi≦105)と書き換えにかかる時間Ti(1≦Ti≦500)が書かれている。
出力
時間内に書き換えられる書類の重要度の合計の最大値を、1行に出力せよ。
以上、技術室奥プログラミングコンテスト#2 B問題より引用。
細かい話は抜きにしてC++での漸化式による解法をPHPで書き直したコードを以下からどうぞ。
<?php
define('MAX_N', 500);
define('MAX_M', 500);
$input = explode(' ', trim(fgets(STDIN)));
$note_count = $input[0];
$remaining_time = $input[1];
$w = array_fill(0, MAX_N, 0);
$v = array_fill(0, MAX_M, 0);
$tmp1 = array_fill(0, MAX_N + 1, 0);
$tmp2 = array_fill(0, MAX_M + 1, 0);
$dp = array($tmp1, $tmp2);
for ($k=0; $k < $note_count; $k++) {
$input = explode(' ', trim(fgets(STDIN)));
$w[$k] = $input[1];
$v[$k] = $input[0];
}
for ($j = 0; $j <= $remaining_time; $j++) {
$dp[$note_count][$j] = 0;
}
for ($i = $note_count - 1; $i >= 0; $i--) {
for ($j = 0; $j <= $remaining_time; $j++) {
if ($j < $w[$i]) {
$dp[$i][$j] = $dp[$i + 1][$j];
} else {
$dp[$i][$j] = max($dp[$i + 1][$j], $dp[$i + 1][$j - $w[$i]] + $v[$i]);
}
}
}
echo $dp[0][$remaining_time]."\n";