【競プロ】1日1AC : EDPC D, E問題【動的計画法】

今日で3回目です。Educational DP Contestの問題を解いていきます。
過去記事はこちら。

【競プロ】1日1AC : EDPC A, B問題【動的計画法】

2020年3月25日

【競プロ】1日1AC : EDPC C問題【動的計画法】

2020年3月26日

今回の問題は今までよりも複雑になりますが、基本は同じなので整理しながら理解していきましょう。

1 D問題
2 E問題
3 終わりに

D問題

DPといえば、みたいな問題です。ナップサックDPと呼ばれています。

実装の都合上、品物に振られる番号は \(0,1,\cdots ,N-1\) とします。

まず配列dpをどう定義するか考えましょう。品物に関する変数 \(i\) 、重さの制限に関する変数 \(j\) が必要になりそうだと予想できますね。

\(dp^j_{i+1}\) を「品物 \(0,1,\cdots ,i\) から、重さが \(j (0 \leq j \leq W)\) 以下となるように品物を取った時の価値の最大値」とします。
品物 \(i\) の重さ、価値を \(w_i,v_i\) とします。

\(dp^j_i (0\leq j \leq W)\) がわかっている時、\(dp^j_{i+1} (0\leq j \leq W)\) を求められるでしょうか。

\(W\) 以下の任意の重さ制限の下で、\(i-1\) までの品物を使った時の価値の最大値はわかるので、品物 \(i\) の扱いを考えます。

\(j < w_i\) だとすると、ナップサックに入れることはできません。すなわち、\(dp^j_{i+1}=dp^j_i\) が成り立ちます。

そうではない時、ナップサックに品物を入れられるのでその場合を考えます。品物 \(i\) を入れる時の価値の最大値は \(dp^j_i+v_i\) と考えてしまうかもしれませんが違います。下の図を見てください。

\(dp^j_i\) は価値が最大になるように、重さ \(j\) 以下で品物 \(0,1,\cdots ,i-1\) を詰めた状態です。基本的に、ここからさらに品物を詰め込むことはできません。（図の下の状態）

そこで、先に品物 \(i\) を入れ、その後で残りの重さ制限 \(j-w_i\) の下で価値が最大になるように品物 \(i-1\) までを入れればいいでしょう。（図の上の状態）（\(dp^j_i\) の任意の \(j\) における値は既にわかっている前提で考えているので、この値は利用可能です。）

また、あえて品物を入れない場合の価値 \(dp^j_i\) も \(dp^j_{i+1}\) の候補となるでしょう。

以上をまとめると、

\[
dp^j_{i+1}=\begin{cases}
dp^j_i & (j < w_i) \\
\max \{dp^j_i,dp^{j-w_i}_{i}+v_i\} & (otherwise)
\end{cases}
\]

であることが分かります。実装は以下のようにできるでしょう。

#include <bits/stdc++.h>
using namespace std;

int N,W;
int N_MAX = 100; int W_MAX = 100000;
vector<int> w(N_MAX),v(N_MAX);
vector<vector<long long>> dp(N_MAX + 1,vector<long long>(W_MAX,0));

int main(){
    cin >> N >> W;
    for(int i = 0;i < N;i++) cin >> w[i] >> v[i];
    
    for(int i = 0;i < N;i++){
        for(int j = 0;j <= W;j++){
            if(j < w[i])
                dp[i+1][j] = dp[i][j];
            else 
                dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]] + v[i]);
        }
    }
    cout << dp[N][W] << endl;
}

初期条件は \(dp^0_0=0\) だけで十分です。出力すべき値は \(dp^W_N\) です。

E問題

D問題と設定は同じですが制約が違います。先ほどは計算量 \(\mathcal{O}(NW)\) でできましたが、今回は \(W\leq 10^9\) なので間に合いません。
そこで、パラメータを変えてみましょう。

\(dp^j_i\) を「品物 \(0,1,\cdots ,i\) から、価値が \(j\) 以上となるように品物を取れるような重さの最小値」とします。ややこしいので答えを求める時のことを先に考えます。
取りうる価値の最大値は \(100\cdot 10^3=10^5\) なので、\(j=10^5,10^5-1,\cdots\) を順に試していき、その価値が初めて重さ \(W\) で実現できる時の \(j\) が答えとなります。
このようなコードを書けばいいでしょう。

int ans = 100000;
while(dp[N][ans] > W) ans--;

では \(dp^j_i\) について考えますが、先ほどと同様に考えることで

\[
dp^j_{i+1}=\begin{cases}
dp^j_i & (j < v_i) \\
\mathrm{min} \{dp^j_{i},dp^{j-v_i}_{i}+w_i\} & (otherwise)
\end{cases}
\]

という式が立てられるのが分かるでしょうか。（手抜きだなんて言わないで...。）

実装も先ほどとほぼ同じになります。

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1LL << 60;

int N,W;
int N_MAX = 100, W_MAX = 1000000000, V_SUM_MAX = 100000;
vector<int> w(N_MAX), v(N_MAX);
vector<vector<long long>> dp(N_MAX + 1,vector<long long>(V_SUM_MAX + 1,INF));
 
int main(){
    cin >> N >> W;
    for(int i = 0;i < N;i++) cin >> w[i] >> v[i];

    dp[0][0] = 0;
    for(int i = 0;i < N;i++){
        for(int j = 0;j <= V_SUM_MAX;j++){
            if(j < v[i])
                dp[i+1][j] = dp[i][j];
            else
                dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]] + w[i]);
        }
    }
    int ans = V_SUM_MAX;
    while(dp[N][ans] > W) ans--;
    cout << ans << endl; 
}

ここではdpはINFで初期化します。また、初期条件 \(dp^0_0=0\) が必要です。