動的計画法が困難なナップザック問題

問題

D: ナップサック問題 - AtCoder Beginner Contest 032 | AtCoder

解法

この問題はナップザック問題を応用したものである。入力値は以下の3つの条件のどれかが当てはまる

  1. N <= 30 のケース
  2. それぞれの荷物の価値Viが1000以下のケース
  3. それぞれの荷物の重さWiが1000以下のケース

それぞれのケースについて考える。

1. N <= 30 のケースはDPできない

このケースでは価値と重みに制約がないため、動的計画法は困難。 今回の問題では、価値と重さの最大値はともに109である。Nが最大値30の場合、動的計画法をするためには、(30*10^9)^2 を格納する2重配列が必要となる。しかし、この量のメモリーを確保することはできない。


そこで、全列挙を考えてみる。それぞれの荷物に関して、リュックサックに入れる場合と入れない場合の2通りが存在するので、計算量はO(2N)となる。N = 30の時、2^30 = 約10^9 でギリギリ間に合わなさそう。

よって工夫が必要である。

http://www.slideshare.net/chokudai/abc032

2. それぞれの荷物の価値Viが1000以下のケース

この条件の時は、荷物の総和は最大でN*Vi = 200 * 10000 = 約10^6となり、メモリーを確保できる計算量になる。 よって以下の漸化式を立てて動的計画法する。

  • i: 荷物のインデックス
  • j: 価値の総和
  • dp[i][j]: i番目までの荷物を操作した時、価値の総和がjの時の最小の重さ

dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);

dpに保持するものは「重さ」であり、いっぱい荷物を入れたいので重さが小さい物を毎回採用していく。

最後に、dp[N - 1][j] の値の中でナップザックの容量を超えないという条件で最大なjが答えになる。

3. それぞれの荷物の重さWiが1000以下のケース

これは一般的なナップザック問題にある。

  • i: 荷物のインデックス
  • j: 重みの総和
  • dp[i][j]: i番目までの荷物を操作した時、重みの総和がjの時の最大の価値

dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);

最後に、dp[N - 1][j] (0 <= j <= W)の値の中でdpが最大な値が答えになる。

ソースコード