🐜(6/30)

動的計画法，解答見てあ〜ってなることしか出来なくて萎える．

動的計画法01

ナップサック問題

重量と価値が$w_i,v_i$である$N$個の荷物を，重量の総和が$W$を超えないように選んでナップサックに詰め込んだとき，価値の総和の最大値を出力せよ．

手法1

1. メモ化再帰

2. memsetによる初期化

手法2

1. 漸化式からの直接DP(再帰不使用)

メモ化再帰を利用する

$\text{dp}[i][j]$を$i$番目以降の品物を重量が$j$以下になるようにナップサックに詰め込んだときの価値総和の最大値を表す$2$次元配列とすると， 取り出さない状態と取り出して価値を比べた状態で 最大の方を選んでいけば良い．呼び出す際はrec(0,W)で再帰的に探索させてやれば良い．

メモ化再帰を用いないと再帰の深度が高くなり，計算量は $O(2^{n})$ となるが，メモ化を用いることで $O(NW)$まで減らすことができる．

int dp[1001][1001];

int rec(int i, int j)
{
    if (dp[i][j] >= 0)
        return dp[i][j];
    int res;
    if (i == N)
        return res = 0;
    else if (j < w[i])
        return res = rec(i + 1, j);
    else
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);
    return dp[i][j] = res;
}

int main()
{
    cin >> N >> W;
    memset(dp, -1, sizeof(dp));
    REP(i, N)
    {
        cin >> w[i];
    }
    REP(i, N)
    {
        cin >> v[i];
    }
    cout << rec(0, W) << endl;
    return 0;
}

漸化式を用いる

上記の漸化式の他，以下のように考えることが可能である．

今度は$\text{dp}[i+1][j]$を$i$番目までの品物から重量が$j$以下になるようにナップサックに詰め込んだときの価値総和の最大値を表す$2$次元配列とすると，

となる．漸化式を立てることができればforを用いて単純に以下のように実装することも可能．

計算量は見ての通り$O(NW)$で済む．

int dynamic()
{
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j <= W; j++)
        {
            if (w[i] > j)
            {
                dp[i + 1][j] = dp[i][j];
            }
            else
            {
                dp[i + 1][j] = max(dp[i][j],
                                   dp[i][j - w[i]] + v[i]);
            }
        }
    }
    return dp[N][W];
}

動的計画法02

重量と価値が$w_i,v_i$である$N$個の荷物を，重量の総和が$W$を超えないように選んでナップサックに詰め込んだとき，価値の総和の最大値を出力せよ．ただし，同一の荷物を複数詰め込んでも良い．

$\text{dp}[i+1][j]$を計算するに当たっては，荷物$i$を$k$個選んだうちの価値最大を格納すれば良いので，ナイーブに実装するなれば， $$ \text{dp}[i+1][j]\leftarrow\max(\text{dp}[i][j],{\text{dp}[i][j-kW[i]]+kV[i]|1\leq k}) $$ となるが，これでは計算量が$O(nW^{2})$となる．

ここでdpテーブルに着目してみると，$\text{dp}[i+1][j-W[i]]$にて，すでに荷物$~i~$を$k-~1$ 個選んだときの荷物の最大値が出ている．よって以下のようにすることで計算量を減らせる．

$$ \text{dp}[i+1][j]\leftarrow\max(\text{dp}[i][j],\text{dp}[i+1][j-W[i]]+V[i]) $$

(もちろん$j<W[i]$の場合分けを忘れずに！！)

int dp[1001][1001];
int N, W[1000], V[1000], w;

int dynamic()
{
    REP(i, N)
    {
        REP(j, w + 1)
        {
            if (j < W[i])
            {
                dp[i + 1][j] = dp[i][j];
                continue;
            }
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - W[i]] + V[i]);
        }
    }
    return dp[N][w];
}