結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
![]() |
提出日時 | 2019-02-27 06:17:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
// 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 constraintsusing 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;elseng = 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) {// dropstk.emplace(i + 1, now_value, rest);// adoptif(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;}