0-1 ナップサック 個数x容量の表を埋めるVer (N=100, W=10000, よくある形) O(NW)

制約

  • 荷物数N=100
  • バッグの容量の最大値W=10000
  • 買うか買わないか(1 or 0)

その他

解き方

  • その１：dp[i][j]
  • その２：メモ化再帰 rec(i, j)

Quiz

https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_B

AC code

https://onlinejudge.u-aizu.ac.jp/status/users/peroon/submissions/1/DPL_1_B/judge/3754207/C++14

感想

  • ナップサックはいろいろな亜種があるのでそれぞれソラで書けるようにしたい

code

// i番目以降を見て
// jキャパシティに入る最大の価値
ll dp[101][10001];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N, C; // C : capacity
    cin >> N >> C;

    vector<ll> V(N);
    vector<ll> W(N);
    FOR(i, 0, N){
        cin >> V[i]; 
        cin >> W[i];
    }

    for(int i=N-1; i>=0; i--){
        FOR(j, 0, C+1){
            if(W[i]>j){
                // 入らない
                dp[i][j] = dp[i+1][j];
            }
            else{
                ll v0 = dp[i+1][j];
                ll v1 = dp[i+1][j-W[i]] + V[i];
                dp[i][j] = max(v0, v1);
            }
        }
    }
    p(dp[0][C]);
    return 0;
}