動的計画法 ナップサック問題を学ぶ

AtCoder 版！蟻本 (初級編)

今日からAtCoder 版！蟻本 (初級編)の記事を読み進めましょう！
蟻本とはプログラミングコンテストチャレンジブックの事です。
この本を読み進めてAtCoderに類似する問題があれば挑戦していきます。

動的計画法（DP: dynamic programming）とは？

値を覚えて再利用することです。

例題 2-3-1　01ナップサック問題

問題は蟻本を参照してください。

• まず全探索による解法
• O(２^n)の計算量

C+

# include<iostream>
# include<vector>
# include<algorithm>
# include<iomanip>
# include<utility>
# include<iomanip>
# include<map>
# include<cmath>
# include<cstdio>

# define rep(i,n) for(int i=0; i<(n); ++i)
# define pai 3.1415926535897932384

using namespace std;
using ll =long long;
using P = pair<int,int>;

# define MAX_N 10
int n, W;
int w[MAX_N];
int v[MAX_N];

int dfs(int i, int j){
    int res=0;
    if(i==n){
        res=0;
    }else if(j<w[i]){
        res = dfs(i+1, j);
    }else{
        res = max(dfs(i+1, j), dfs(i+1, j-w[i])+ v[i]);
    }
    return res;
}
 
int main(int argc, const char * argv[]) {

    cin >> n >> W;
    rep(i, n){
        cin >> w[i] >> v[i];
    }
    
    cout << dfs(0, W) << endl;
    return 0;
}

• O(２^n)の為、大きな値に対応できません。
• そこでDPの考えにより計算結果を保持しましょう。

C++

# include<iostream>
# include<vector>
# include<algorithm>
# include<iomanip>
# include<utility>
# include<iomanip>
# include<map>
# include<cmath>
# include<cstdio>

# define rep(i,n) for(int i=0; i<(n); ++i)
# define pai 3.1415926535897932384

using namespace std;
using ll =long long;
using P = pair<int,int>;

# define MAX_N 10
# define MAX_W 10

int n, W;
int w[MAX_N];
int v[MAX_N];

int dp[MAX_N][MAX_W];

int dfs(int i, int j){
    if(dp[i][j]>=0){
       return dp[i][j];
    }
    
    int res=0;
    if(i==n){
        res=0;
    }else if(j<w[i]){
        res = dfs(i+1, j);
    }else{
        res = max(dfs(i+1, j), dfs(i+1, j-w[i])+ v[i]);
    }
    return dp[i][j] = res;
}
 
int main(int argc, const char * argv[]) {

    cin >> n >> W;
    rep(i, n){
        cin >> w[i] >> v[i];
    }
    
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, W) << endl;
    return 0;
}

上記のプログラムから、下記の漸化式が成り立っている。
（漸化式とは、数列の各項を、その前の項から順にただ１通りに定める規則を表す等式のことです。）
dfsによる記載をしなくてもループ文による記載が可能。

漸化式

dp[i][j]=0
dp[i][j]={
    dp[i+1][j](j<w[i]の時)
    max(dp[i+1][j], dp[i+1][j-w[i]]+v[i])(それ以外)
}

上記の考えから、

C++

int main(int argc, const char * argv[]) {

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

が成り立つ。
そしてiのループを順列にする。

漸化式

dp[0][j]=0
dp[i+1][j]={
    dp[i][j](j<w[i]の時)
    max(dp[i][j], dp[i][j-w[i]]+v[i])(それ以外)
}

上記の漸化式から、

C++

int main(int argc, const char * argv[]) {

    cin >> n >> W;
    rep(i, n){
        cin >> w[i] >> v[i];
    }
    
    memset(dp, 0, sizeof(dp));
    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;
    
    return 0;
}

となる。
ここから例題を解きましょう。

0-1 ナップザック問題

問題はリンクから確認してください。

例題そのままです。
異なるのは入力の順番がvi, wiの順の１点です。

C++

# include<iostream>
# include<vector>
# include<algorithm>
# include<iomanip>
# include<utility>
# include<iomanip>
# include<map>
# include<cmath>
# include<cstdio>

# define rep(i,n) for(int i=0; i<(n); ++i)
# define pai 3.1415926535897932384

using namespace std;
using ll =long long;
using P = pair<int,int>;

# define MAX_N 100
# define MAX_W 10000

int N, W;
int w[MAX_N];
int v[MAX_N];
int dp[MAX_N+1][MAX_W+1];
 
int main(int argc, const char * argv[]) {

    cin >> N >> W;
    rep(i, N){
        cin >> v[i] >> w[i];
    }
    
    memset(dp, 0, sizeof(dp));
    
    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;
    
    return 0;
}