perogram

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

制約

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

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

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];
    }

    // i番目以降を見て
    // jキャパシティに入る最大の価値
    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;
}