3624:Charm Bracelet

keyword

動的計画法　ナップザック問題　C++

概要

01ナップザック問題を解く。サイズは個数3500以下、重さ400以下、価値100以下、容量13000以下。
dp[n番目まで見た][現在の容量]でDP。

int main(){
    int n, m, i, j;
    n = readint();
    m = readint();

    REP(i,n){
        wws[i] = readint();
        ds[i] = readint();
    }

    m++;
    REP(i,2)REP(j,m)dp[i][j] = -1;

    dp[0][0] = 0;
    dp[0][wws[0]] = ds[0];

    FOR(i,1,n){
        int next = i&1, cur = 1 - next;
        REP(j,m){
            if(dp[cur][j] >= 0){
                if(dp[next][j] < dp[cur][j])
                    dp[next][j] = dp[cur][j];
                if(j + wws[i] < m &&
                        dp[next][j+wws[i]] < dp[cur][j] + ds[i])
                    dp[next][j+wws[i]] = dp[cur][j] + ds[i];
            }
        }  
    }

    printf("%d\n",*max_element(dp[1- (n&1)],dp[1 - (n&1)]+m));
    return 0;
}