結果

問題 No.626 Randomized 01 Knapsack
ユーザー はむこはむこ
提出日時 2017-12-13 11:19:11
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 551 ms / 2,000 ms
コード長 3,117 bytes
コンパイル時間 2,135 ms
コンパイル使用メモリ 169,300 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-06 03:28:24
合計ジャッジ時間 6,330 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 4 ms
5,376 KB
testcase_07 AC 14 ms
5,376 KB
testcase_08 AC 6 ms
5,376 KB
testcase_09 AC 39 ms
5,376 KB
testcase_10 AC 15 ms
5,376 KB
testcase_11 AC 87 ms
5,376 KB
testcase_12 AC 315 ms
5,376 KB
testcase_13 AC 212 ms
5,376 KB
testcase_14 AC 76 ms
5,376 KB
testcase_15 AC 224 ms
5,376 KB
testcase_16 AC 295 ms
5,376 KB
testcase_17 AC 241 ms
5,376 KB
testcase_18 AC 220 ms
5,376 KB
testcase_19 AC 290 ms
5,376 KB
testcase_20 AC 520 ms
5,376 KB
testcase_21 AC 282 ms
5,376 KB
testcase_22 AC 551 ms
5,376 KB
testcase_23 AC 546 ms
5,376 KB
testcase_24 AC 76 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using P = pair<ll, ll>;
#define INF (ll)1e18

#define SIZE 2001
ll n, W; 
ll best_feasible = 0;
vector<P> ab;
vll v, w;

// [0, i)がb[0, i)のように確定していて、その後が不確定である時、線形緩和問題を解く
// 返り値(double, bool) = (緩和問題の最適解, その最適解が元問題の制約を厳密に満たすか)
pair<double, bool> solveRelaxationProblem(ll i, bitset<SIZE>& b) {
    double ans = 0;
    double w_now = W;
    rep(j, i) ans += b[j] * v[j], w_now -= b[j] * w[j];
    bool faf = 1;
    repi(j, i, n) {
        double tmp = min<double>(w_now, w[j]);
        faf &= (tmp == 0 || tmp == w[j]);
        w_now -= tmp;
        ans += tmp * (v[j] * 1.0 / w[j]);
    }
    return make_pair(ans, faf);

}

// [0, i)がb[0, i)のように確定していてその後が不確定である時、線形緩和問題を解く
// （負荷情報として、確定しているところの価値総和がv_now, 重さ総和w_nowを持っておく）
//
// 返り値double = 最適解
ll dfs(ll i, bitset<SIZE>& b, ll v_now, ll w_now) {
//    string s = b.to_string(); reverse(begin(s), end(s)); cout << s << endl;
    if (i == n) { best_feasible = max<ll>(best_feasible, v_now); return v_now; }

    auto relax_p = solveRelaxationProblem(i, b);
    double relax = relax_p.first; 
    double satisfiability = relax_p.second;

    if (satisfiability) { best_feasible = max<ll>(best_feasible, relax); return relax; } // 緩和問題の解を与える選び方が元問題の制約を満たしているので、それが最適でもある
    if (relax < best_feasible) { return -INF; } // 緩和問題の解が、今までの最善許容解に達さないので、探索しても無駄

    ll tmp = -INF;

    // 解がありそうな方を先に分岐するのが極めて重要！今回、0->1の順番で分岐するとTLEする。
    // 1を分岐
    if (w_now+w[i]<=W) {
        b[i] = 1;
        chmax(tmp, dfs(i+1, b, v_now+v[i], w_now+w[i]));
        b[i] = 0;
        chmax(best_feasible, tmp);
    }
    // 0を分岐
    chmax(tmp, dfs(i+1, b, v_now, w_now));
    chmax(best_feasible, tmp);

    return tmp;
}
int main(void) {
    cin >> n >> W;
    ab.resize(n); rep(i, n) cin >> ab[i].first >> ab[i].second;
    sort(ab.begin(), ab.end(), [&](P l, P r) { return l.first*r.second>r.first*l.second; });
    v = vll(n), w = vll(n);
    rep(i, n) {
        v[i] = ab[i].first;
        w[i] = ab[i].second;
    }

    ll w_now = W;
    rep(i, n) {
        if (w[i] <= w_now) {
            w_now -= w[i];
            best_feasible += v[i];
        }
    }
    
    bitset<SIZE> b;
    cout << dfs(0, b, 0, 0) << endl;;

    return 0;
}
0