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

#AtCoder 版！蟻本 (初級編)
今日から[AtCoder 版！蟻本 (初級編)](https://qiita.com/drken/items/e77685614f3c6bf86f44)の記事を読み進めましょう！
[蟻本](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E3%83%81%E3%83%A3%E3%83%AC%E3%83%B3%E3%82%B8%E3%83%96%E3%83%83%E3%82%AF-%E7%AC%AC2%E7%89%88-%EF%BD%9E%E5%95%8F%E9%A1%8C%E8%A7%A3%E6%B1%BA%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E6%B4%BB%E7%94%A8%E5%8A%9B%E3%81%A8%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0%E3%83%86%E3%82%AF%E3%83%8B%E3%83%83%E3%82%AF%E3%82%92%E9%8D%9B%E3%81%88%E3%82%8B%EF%BD%9E-%E7%A7%8B%E8%91%89%E6%8B%93%E5%93%89/dp/4839941068)とはプログラミングコンテストチャレンジブックの事です。
この本を読み進めてAtCoderに類似する問題があれば挑戦していきます。

#動的計画法（DP: dynamic programming）とは？
値を覚えて再利用することです。

##例題 2-3-1　01ナップサック問題
問題は蟻本を参照してください。 

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

```C++: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++: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++: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++: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 ナップザック問題](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp)
問題はリンクから確認してください。

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

```C++: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;
}
```