ABC060D Simple Knapsack解いたんだよ

問題

D: Simple Knapsack - AtCoder Regular Contest 073 | AtCoder

dp解

$dp[i][j] := i$ 個使用して重さの総和が $j+w_0 i$ となるときの価値の最大値
とする.
ここで重さを直接持つと配列に収まらないので $w_i$ の代わりに $w_i - w_0$ を使用することで配列に収まるようにできる

注意点

内部のループは逆に回さないと同じ荷物を何度も使用できてしまうので注意

コード

ll N,W;
ll w[128],v[128];
ll dp[128][512];
 
int main(){
    cin >> N >> W;
    rep(i,N) cin>>w[i]>>v[i];
 
    ll sum=0;
    rep(i,N){
        ll ww = w[i]-w[0];
        // 荷物iを複数回使わないように逆に回す
        for(int j=i;j>=0;j--){  // 荷物iを含まないでj個
            for(int k=sum;k>=0;k--){    // 荷物iを含まない時の重さがk
                dp[j+1][k+ww] = max(dp[j+1][k+ww],dp[j][k]+v[i]);
            }
        }
        sum += ww;
    }
 
    ll ans=0;
    for(int i=0;i<=N;i++){
        for(int j=0;j<=sum;j++){
            if(w[0]*i+j>W) continue;
            ans = max(ans,dp[i][j]);
        }
    }
    cout << ans << endl;
}