ナップザック

int npz(vector<pair<int,int>> v,int w){
    //{重さ、価値}、重さ制限
    int n = v.size();
    vector<vector<int>> dp(n,vector<int>(w+1,-1));
    dp[0][0] = 0;
    if(v[0].first <= w){
        dp[0][v[0].first] = v[0].second;
    }
    for(int i = 0;i < n-1;i++){
        for(int j = 0;j <= w;j++){
            if(dp[i][j]==-1)continue;
            if(j+v[i+1].first <= w){
            dp[i+1][j+v[i+1].first] = max(dp[i+1][j+v[i+1].first],dp[i][j]+v[i+1].second);
            }
            dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
        }   
    }
    int ans = -1;
    for(int j = 0;j <= w;j++){
        ans = max(ans,dp[n-1][j]);
    }

    return ans;
}