01ナップサックの集大成!? 3つのナップサック解法を場合分ける「D - ナップサック問題」

• Quiz (2016/01)
  • https://atcoder.jp/contests/abc032/tasks/abc032_d
• AC
  • https://atcoder.jp/contests/abc032/submissions/19071044
• 感想
  • 「やるだけ」と放置していたが、復習に丁度いいのではと思って解いたらその通りで、よい復習になった
• 解法
  • 入力データを見て「半分全列挙」「valueが小さい場合のナップサック」「weightが小さい場合のナップサック」で解法分岐させる

// 半分全列挙VER
// N <= 30
// value <= 10^9
// weight <= 10^9
// capacity <= 10^9
ll knapsack_by_split(ll N, ll C, VI V, VI W){
  const int N_MAX=30;
  debug("knapsack_by_split");
  // 長さ30にする
  rep(i,N_MAX-N){
    V.push_back(0);
    W.push_back(0);
  }
  N=N_MAX;

  // (weight, value)のリストをいい感じに返す
  auto f = [](ll N, VI V, VI W){
    vector<PII> ret;
    rep(f,1<<N){
      ll val=0;
      ll wei=0;
      rep(i,N){
        if(f>>i&1){
          // 採用
          val += V[i];
          wei += W[i];
        }
      }
      ret.emplace_back(wei,val);
    }
    sort(ALL(ret));
    ll max_value = ret[0].second;
    // このweightを使うなら少なくともこのvalueを達成できるというのを入れる
    FOR(i,1,SZ(ret)){
      chmax(max_value, ret[i].second);
      ret[i].second = max_value;
    }
    return ret;
  };

  // 15個ずつに分ける
  vector<PII> A,B;
  {
    VI v,w;
    rep(i,N/2){
      v.push_back(V[i]);
      w.push_back(W[i]);
    }
    A = f(N/2, v, w);
  }
  {
    VI v,w;
    FOR(i,N/2,N){
      v.push_back(V[i]);
      w.push_back(W[i]);  
    }
    B = f(N/2, v, w);
  }
  
  // A側のそれぞれに対してB側を2分探索して容量C以内でマッチングさせる
  ll ma=0;
  for(auto pa : A){
    ll w = pa.first;
    ll v = pa.second;
    if(w>C)continue;
    
    // PII key = {C-w, 0LL};
    PII key = {C-w, inf};

    auto it = upper_bound(ALL(B), key);
    ll value_sum;
    if(it==B.begin()){
      value_sum = v;
    }else{
      it--;
      value_sum = v + it->second;
    }
    chmax(ma,value_sum);
  }
  return ma;
}

// N<=200
// weight <= 10^9
// value <= 1000
ll knapsack_by_small_value(ll N, ll C, VI V, VI W){
  debug("knapsack_by_small_value");
  VV dp(205, VI(210000, inf));
  // i番目まで見て
  // 価値jを達成する時に必要な最小の重さ
  dp[0][0]=0;
  rep(i,N){
    ll v = V[i];
    ll w = W[i];
    rep(j,200001){
      // j : 現在価値
      // とる
      chmin(dp[i+1][j+v], dp[i][j]+w);
      // とらない
      chmin(dp[i+1][j], dp[i][j]);
    }
  }
  ll ma=0;
  rep(v,210000){
    if(dp[N][v]<=C){
      chmax(ma,v);
    }
  }
  return ma;
}

// value <= 10^9
// weight <= 1000
// N <= 200
ll knapsack_by_small_weight(ll N, ll C, VI V, VI W){
  debug("knapsack_by_small_weight");
  VV dp(205, VI(210000, 0));
  // iまで見て
  // 重さjでの最大価値
  rep(i,N){
    ll v=V[i];
    ll w=W[i];
    rep(j,200000+1){
      // j : 現在の重さ
      // とる
      chmax(dp[i+1][j+w], dp[i][j]+v);
      // とらない
      chmax(dp[i+1][j], dp[i][j]);
    }
  }

  // Cが10^9もありうる
  C = min(200000LL,C);
  ll ma=0;
  rep(w,C+1){
    chmax(ma, dp[N][w]);
  }
  return ma;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,C;
    cin>>N>>C;

    VI V(N);
    VI W(N);
    rep(i, N){
      cin >> V[i] >> W[i];
    } 

    ll ans;
    if(MAX(V)<=1000){
      ans = knapsack_by_small_value(N,C,V,W);
    }
    else if(MAX(W)<=1000){
      ans = knapsack_by_small_weight(N,C,V,W);
    }
    else{
      // N<=30
      ans = knapsack_by_split(N,C,V,W);
    }

    p(ans);
    
    return 0;
}