3napsacks.cpp

#include <bits/stdc++.h>

using namespace std;

#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define mp make_pair
#define fst first
#define snd second
#define pb push_back

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//#define int int32_t
//#define ll int64_t
#define uint uint32_t
#define ull uint64_t
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll INF = 1LL << 60;    //1はint
const double EPS = 1e-10;

template<class T>
ll stoi(T &str) {
    ll ret;
    stringstream ss;
    ss << str;
    ss >> ret;
    return ret;
}

template<class T>
string toString(T i) {
    stringstream ss;
    ss << i;
    return ss.str();
}

template<class T>
void amax(T &a, T &b) { if (a < b)a = b; }

int N, W;
int *w;
int *v;
bool smallW = true, smallV = true, smallN = true;
int vsum=0;
void dataChecker() {
    rep(i, N) {
        vsum+=v[i];
        if (v[i] > 1000)
            smallV = false;

        if (w[i] > 1000)
            smallW = false;
    }
    if (N > 30)
        smallN = false;
}

int main() {
    scanf("%d %d", &N, &W);
    w = new int[N];
    v = new int[N];
    rep(i, N)scanf("%d %d", &v[i], &w[i]);
    //cin>>v[i]>>w[i];
    dataChecker();

    if (smallW) {
        ll dp[N + 1][W+1];
        fill(dp[0], dp[N + 1], -1);   //開始イテレータ，末尾イテレータ，セットする値
        dp[0][0] = 0;               //dp[item][weight]=value
        ll ans = 0;
        rep(i, N) {
            rep(j, W+1) {
                if (dp[i][j] != -1) {//更新条件
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);     //使わない場合
                    if (j + w[i] <= W) {                            //使う場合
                        dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
                        amax(ans, dp[i + 1][j + w[i]]);
                    }
                }
            }
        }
        cout << ans << endl;
    } else if (smallV) {
        ll dp[N + 1][vsum+1001];       //ある価値で最も小さい重さをメモしていく
        fill(dp[0], dp[N + 1], INF);    //開始イテレータ，末尾イテレータ，セットする値
        // 先頭はdp[0][0] 末尾はdp[N+1][0]
        dp[0][0] = 0;                   //dp[item][weight]=value
        int ans = 0;
        rep(i, N) {
            rep(j, vsum+1) {
                if (dp[i][j] != -1) {//更新条件
                    dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);     //使わない場合
                    dp[i + 1][j + v[i]] = min(dp[i + 1][j + v[i]], dp[i][j] + w[i]);
                }
            }
        }
        rep(i,vsum+1){
            if(dp[N][i]<=W)
                amax(ans,i);
        }

        cout << ans << endl;

    } else {
        ll n2=N/2;
        vector<pll> vec1(n2*n2);            //w,v
        rep(i,1<<n2){
            ll wtmp=0;
            ll vtmp=0;
            rep(j,n2){
                if(i>>j & 1){
                    wtmp+=w[j];
                    vtmp+=v[j];
                }
            }
            vec1.pb(mp(wtmp,vtmp));
        }
        sort(vec1.begin(),vec1.end());
        int m=1;
        REP(i,1,1<<n2){
            if(vec1[i-1].second<vec1[i].second){
                vec1[m++]=vec1[i];
            }
        }
        ll ans=0;
        rep(i,1<<(N-n2)){
            ll wtmp=0;
            ll vtmp=0;
            rep(j,N-n2){
                if(i>>j & 1){
                    wtmp+=w[n2+j];
                    vtmp+=v[n2+j];
                }
            }
            if(wtmp<=W) {
                ll num = (lower_bound(vec1.begin(), vec1.begin() + m, mp(W - wtmp, INF))-1)->second +vtmp;
                amax(ans, num);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}