問題

解法

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

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

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

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

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

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

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

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

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