ナップサック問題の動的計画法をPHPで書く

問題文

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";

LINEで送る
Pocket

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です


*