典型ナップサックを1次元配列で解く。
※一番PV数が多いので、ちょっと直しました(2020/5/24)
例題として、 B - 書き換え(Rewrite)を使います。
まずはこのコードを見てください。
#include<bits/stdc++.h> using namespace std; int main(){ int N,M; cin >> N >> M; vector<int>V(N),T(N); for(int i = 0; i < N; ++i){ cin >> V[i] >> T[i]; } vector<int>dp(M + 1,0); for(int i = 0; i < N; i++) for(int t = M; t >= 0;t--){ if(t + T[i] <= M) dp[t + T[i]] = max(dp[t + T[i]], dp[t] + V[i]); } cout << *max_element(dp.begin(), dp.end()) << endl; }
シンプルですね。時間計算量はですが、空間計算量はで少しお得です。
まずは2次元で考える。
二次元DPで考えると、
個目の書類を見ている時に,時間使ったときの最大値
という漸化式になります。
さて、この問題を1次元配列で解くことを考えます。
時間のときの最大の価値
つまり、どの書類を見ているか、という情報を捨てます。
以下が工夫するポイントです。
後ろ向きに更新する
時間を後ろからなめて、次のように更新します。
for(int t = M; t >= 0; --t)
嬉しいポイントは、値の更新がすでに見たに対して行われます。つまり、番目の書類を重複して更新されることがありません。
荷物を取らない推移ないけど?
必要無いからです。2次元DPの際は,番目の書類まで見た結果を番目にも反映させる必要があるますが、この場合はありません。