w22116972
4/2/2014 - 8:53 AM

0/1 napsack

0/1 napsack

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

void solve(){
        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];
}