いろいろなDP｜動的計画法｜ナップザック

DP 配列を- INF で埋めた DP が解らなかったのでナップザック問題を使って比較してみました。

使う問題はこれ：ナップザック問題 | 動的計画法 | Aizu Online Judge

---

① 普通に普通の 埋めDP

まずは普通に本 *1 で学習したナップザックで解きます。

定義

dp[ i 個の荷物を考慮して ][ 重さが j 以下のとき ] := 達成可能な価値の和の最大値

のとき

個の荷物を考慮したとき、ナップザックには何も入っていないので重さ ，価値の和も となる。
重さ ，価値 の状態は任意の に対して｢重さ 以下｣の条件を満たすため、任意の に対して dp[ 0 ][ j ] := 0 となる。

のとき

番目の荷物の重さ が 以下の場合、ナップザックに 番目の荷物を詰め込むことができると考え、 番目の荷物をナップザックに入れる場合と入れない場合を比較し、より価値の和が大きい方を最大値として更新していきます。

入れる場合
番目の荷物を除外し、 番目までの荷物のみで、重さ 以下のときの価値の最大値が得られるとすると、そこに 番目の荷物の重さ を加えると重さ 以下のときの価値の最大値の候補が得られる。

入れない場合
番目の荷物を除外し、 番目までの荷物のみで、重さ 以下のときの価値の最大値が得られるとすると、そこに 番目の荷物を加えない場合の価値の最大値は、 番目の荷物を除外した価値の和の最大値と同じになる。

のとき

番目の荷物の重さ が を超える場合、「重さ 以下のとき」という条件を満たさないので、上記の入れない場合と同様に 番目の荷物を除外した価値の和の最大値と同じになる。

以上の計算が終わると dp[ N ][ W ] で定義のとおり価値の和の最大値が求まります。

漸化式

　

コード

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N, W;
    cin >> N >> W;
    vector<int> v( N ), w( N );
    REP( i, N )
    {
        cin >> v[ i ] >> w[ i ];
    }
    vector<vector<int>> dp( N + 1, vector<int>( 100001 ) );
    for( int i = 1; i <= N; ++i )
    {
        for( int j = 0; j <= W; ++j )
        {
            if( j >= w[ i - 1 ] )
            {
                dp[ i ][ j ] = max( dp[ i - 1 ][ j ], dp[ i - 1 ][ j - w[ i - 1 ] ] + v[ i - 1 ] );
            }
            else
            {
                dp[ i ][ j ] = dp[ i - 1 ][ j ];
            }
        }
    }
    cout << dp[ N ][ W ] << endl;
    return 0;
}

---

② -INF で埋めるDP

次に、DP配列を予め -INF で埋めるDPを考えます。

定義

• dp[ i 個の荷物を考慮して ][ 重さが j の時 ] := 達成可能な価値の和の最大値
• 達成可能か否かを区別できるように、DP 配列を予め解に成り得ない値で埋めておく。
  価値の和の最大値となるような値が存在しない場合は解として成り得ない値になっていてほしいので、この問題の場合、制約を見ると、 なので、 価値の最大値 を 回足しても非負の整数にならない より小さな値で初期化します。

のとき

①のケースと同様に， 個の荷物で実現可能な唯一の状態は重さ 価値 である。
従って、dp[ 0 ][ 0 ] := 0 となる。

のとき

なる については， 個の荷物では正の重さを実現できないため、実行不可能な状態である。
よって、重さとして有り得ない値（かつ、特別扱いせずに計算を進めても有り得ない値のままでいてくれる）-INF で初期化する。

のとき

番目の荷物の重さ が 以下の場合、ナップザックに荷物を詰め込むことができると考え、 番目の荷物をナップザックに入れる場合と入れない場合を比較し、より価値の和が大きい方を最大値として更新していきます。

入れる場合
番目の荷物を除外し、 番目までの荷物のみで、重さ のときの価値の最大値が得られるとすると、そこに 番目の荷物の重さ を加えると重さ のときの価値の最大値が得られる。

入れない場合
番目の荷物を除外し、 番目までの荷物のみで、重さ のときの価値の最大値が得られるとすると、そこに 番目の荷物を加えない場合の価値の最大値は、 番目の荷物を除外した価値の和の最大値と同じになる。

のとき

番目の荷物の重さ が を超える場合、「重さ のとき」という条件を満たさないので、上記の入れない場合と同様に 番目の荷物を除外した価値の和の最大値と同じになる。

以上の計算が終わると、 個全ての荷物を考慮した各重さ のときの価値の和の最大値が dp[ N ][ j ] で得られますので、dp[ N ][ j ] の行の MAX を取ると答えが求まります。

漸化式

コード

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const int INF = 10000000;
int main()
{
    int N, W;
    cin >> N >> W;
    vector<int> v( N ), w( N );
    REP( i, N )
    {
        cin >> v[ i ] >> w[ i ];
    }
    vector<vector<int>> dp( N + 1, vector<int>( 10001, -INF ) );
    dp[ 0 ][ 0 ] = 0;
    for( int i = 1; i <= N; ++i )
    {
        for( int j = 0; j <= W; ++j )
        {
            if( j >= w[ i - 1 ] )
            {
                dp[ i ][ j ] = max( dp[ i - 1 ][ j ], dp[ i - 1 ][ j - w[ i - 1 ] ] + v[ i - 1 ] );
            }
            else
            {
                dp[ i ][ j ] = dp[ i - 1 ][ j ];
            }
        }
    }
    cout << *max_element( ALL( dp.back() ) ) << endl;
    return 0;
}

コード：https://wandbox.org/permlink/RK5gfohRlQwd7cKE

---

まとめ

普通の DP と INF 埋め DP の違う点

• ①の DP が 以下の価値の最大値を求めるのに対し、② の -INF で埋める DP は 重さがちょうど の時の価値の和の最大値を求めるという違いがある事が判った。
• また、それにより計算後の解の得方にも違いがある事が判った。

---

*1:TLE本など