ABC 32 D - ナップサック問題 ( 01Knapsack, 3 solutions )

D: ナップサック問題 - AtCoder Beginner Contest 032 | AtCoder
いい練習になった。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;

int n, c;
int v[ MAXN ], w[ MAXN ];

void solve1(){ // n <= 30
    vector<pll> set1;
    int s1 = n / 2;
    for(int i = 0; i < ( 1 << s1 ); ++i){
        ll vsum = 0LL, wsum = 0LL;
        for(int j = 0; j < s1; ++j){
            if( ( i >> j ) & 1 )
                vsum += v[ j ],
                wsum += w[ j ];
        }
        set1.push_back( pll( wsum, vsum ) );
    }
    sort( set1.begin(), set1.end() );
    set1.erase( unique( set1.begin(), set1.end() ), set1.end() );
    
    int vi = 1;
    for(int i = 1; i < set1.size(); ++i)
        if( set1[ i - 1 ].second < set1[ i ].second )
            set1[ vi++ ] = set1[ i ];
    set1.erase( set1.begin() + vi, set1.end() );
    
    ll ans = 0LL;
    int s2 = n - s1;
    for(int i = 0; i < ( 1 << s2 ); ++i){
        ll vsum = 0LL, wsum = 0LL;
        for(int j = 0; j < s2; ++j){
            if( ( i >> j ) & 1 )
                vsum += v[ s1 + j ],
                wsum += w[ s1 + j ];
        }
        int idx = upper_bound( set1.begin(), set1.end(), pll( c - wsum, (ll)( 1e16 ) ) ) - set1.begin();
        if( --idx < 0 ) continue;
        ans = max<ll>( ans, set1[ idx ].second + vsum );
    }
    printf("%lld\n", ans);
}

void solve2(){ // w <= 1000
    vector<ll> dp( c + 1 ); // maximum value when weight is i
    fill( dp.begin(), dp.end(), (ll)( -1e16 ) );
    dp[ 0 ] = 0LL;
    for(int i = 0; i < n; ++i)
        for(int j = c - w[ i ]; j >= 0; --j)
            dp[ j + w[ i ] ] = max<ll>( dp[ j + w[ i ] ], dp[ j ] + v[ i ] );
    printf("%lld\n", *max_element( dp.begin(), dp.end() ));
}

void solve3(){ // v <= 1000
    int mv = *max_element( v, v + n ) * n;
    vector<ll> dp( mv + 1 ); // minimum weight when value is i
    fill( dp.begin(), dp.end(), (ll)( 1e16 ) );
    dp[ 0 ] = 0LL;
    for(int i = 0; i < n; ++i)
        for(int j = mv - v[ i ]; j >= 0; --j)
            dp[ j + v[ i ] ] = min<ll>( dp[ j + v[ i ] ], dp[ j ] + w[ i ] );
    for(int i = mv; i >= 0; --i)
        if( dp[ i ] <= c ){
            printf("%d\n", i);
            return;
        }
}

void solve(){
    if( n <= 30 ) solve1();
    else if( *max_element( w, w + n ) <= 1000 ) solve2();
    else solve3();
}

int main(){
    scanf("%d%d", &n, &c);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &v[ i ], &w[ i ]);
    solve();
    return 0;
}