結果

問題 No.626 Randomized 01 Knapsack
ユーザー lumc_lumc_
提出日時 2019-02-27 06:17:37
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 3,513 bytes
コンパイル時間 1,267 ms
コンパイル使用メモリ 122,076 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-23 04:59:44
合計ジャッジ時間 1,858 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 4 ms
6,944 KB
testcase_12 AC 4 ms
6,944 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 3 ms
6,944 KB
testcase_15 AC 3 ms
6,944 KB
testcase_16 AC 4 ms
6,944 KB
testcase_17 AC 5 ms
6,944 KB
testcase_18 AC 4 ms
6,940 KB
testcase_19 AC 5 ms
6,944 KB
testcase_20 AC 5 ms
6,940 KB
testcase_21 AC 3 ms
6,940 KB
testcase_22 AC 5 ms
6,940 KB
testcase_23 AC 6 ms
6,944 KB
testcase_24 AC 3 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// includes {{{
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
// #include<deque>
// #include<multiset>
// #include<bitset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

// こうですか．そうですよね
// 0 <= z <= 1 を緩和するんですもんね
// EPSの変化やDFSの探索順序，DFSをBFSに変えたらどうなるかなども気になるところです
// EPSいらないね
// doubleいるね，そうだよね
// それ以降で取れるやつがあるかもしれないからね
// 「貪欲に連続を採用」ではなくて，
// 「貪欲に採用し続ける」だった
// なるほどなあ
// いや合っていた

int n, W;

#include <stack>
#include <tuple>
#include <vector>
unsigned long long knapsack01_branch_and_bound(const vector< unsigned long long > &cost,
                                               const vector< unsigned long long > &value,
                                               unsigned long long weight) {
  using size_type = size_t;
  using ull = unsigned long long;
  using item_type = pair< ull, ull >;
  using float_type = double;

  size_type _n = cost.size();
  assert(_n == value.size());
  vector< item_type > items(1);

  for(size_type i = 0; i < _n; i++) {
    assert(cost[i] > 0);
    if(cost[i] <= weight) items.emplace_back(value[i], cost[i]);
  }

  size_type n = items.size() - 1;

  sort(begin(items) + 1, end(items), [&](const item_type &a, const item_type &b) {
    return (float_type) a.first / a.second > (float_type) b.first / b.second;
  });

  vector< ull > value_sum(n + 1), cost_sum(n + 1);

  for(size_type i = 1; i <= n; i++)
    value_sum[i] = value_sum[i - 1] + items[i].first,
    cost_sum[i] = cost_sum[i - 1] + items[i].second;

  ull feasible_best = 0; // this satisfies the constraints

  using state_type = tuple< size_type, ull, ull >;
  stack< state_type > stk;
  stk.emplace(1, 0, weight);

  while(stk.size()) {
    size_type i;
    ull now_value, rest;
    tie(i, now_value, rest) = stk.top();
    stk.pop();

    // feasible_best = max(feasible_best, now_value);
    if(rest == 0) continue;

    size_type ok = i - 1, ng = n + 1;
    while(ng - ok > 1) {
      size_type mid = (ng + ok) >> 1;
      ull extra_cost = cost_sum[mid] - cost_sum[i - 1];
      if(extra_cost <= rest)
        ok = mid;
      else
        ng = mid;
    }

    ull extra_cost = cost_sum[ok] - cost_sum[i - 1];
    ull extra_value = value_sum[ok] - value_sum[i - 1];

    feasible_best = max(feasible_best, now_value + extra_value);

    float_type relax_upper_bound = now_value + extra_value;
    if(ok + 1 <= n)
      relax_upper_bound +=
          (float_type) items[ok + 1].first / items[ok + 1].second * (rest - extra_cost);

    if(floor(relax_upper_bound) <= feasible_best) continue;

    if(i < n) {
      // drop
      stk.emplace(i + 1, now_value, rest);
      // adopt
      if(rest >= items[i].second)
        stk.emplace(i + 1, now_value + items[i].first, rest - items[i].second);
    }
  }

  return feasible_best;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n >> W;
  using ull = unsigned long long;
  vector< ull > value(n), cost(n);
  for(int i = 0; i < n; i++) {
    cin >> value[i] >> cost[i];
  }
  cout << knapsack01_branch_and_bound(cost, value, W) << endl;
  return 0;
}
0