結果

問題 No.626 Randomized 01 Knapsack
ユーザー はむこはむこ
提出日時 2017-12-14 10:02:25
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 502 ms / 2,000 ms
コード長 3,739 bytes
コンパイル時間 2,334 ms
コンパイル使用メモリ 170,464 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 03:26:02
合計ジャッジ時間 5,691 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 5 ms
5,376 KB
testcase_07 AC 6 ms
5,376 KB
testcase_08 AC 6 ms
5,376 KB
testcase_09 AC 10 ms
5,376 KB
testcase_10 AC 17 ms
5,376 KB
testcase_11 AC 59 ms
5,376 KB
testcase_12 AC 283 ms
5,376 KB
testcase_13 AC 7 ms
5,376 KB
testcase_14 AC 13 ms
5,376 KB
testcase_15 AC 116 ms
5,376 KB
testcase_16 AC 239 ms
5,376 KB
testcase_17 AC 192 ms
5,376 KB
testcase_18 AC 170 ms
5,376 KB
testcase_19 AC 242 ms
5,376 KB
testcase_20 AC 502 ms
5,376 KB
testcase_21 AC 7 ms
5,376 KB
testcase_22 AC 210 ms
5,376 KB
testcase_23 AC 438 ms
5,376 KB
testcase_24 AC 6 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 5001
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 = 最適解
bitset<SIZE> ret_b;
void update(bitset<SIZE>& b, ll v_now) {
    if (best_feasible < v_now) {
        best_feasible = v_now;
        ret_b = b;
        cout << ret_b << endl;
    }
}
ll best_feasible_org;
ll dfs(ll i, bitset<SIZE>& b, ll v_now, ll w_now) {
//    cout << best_feasible << endl;
//    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;
        update(b, tmp);
    }
    // 0を分岐
    chmax(tmp, dfs(i+1, b, v_now, w_now));
    update(b, tmp);

    return tmp;
}
int main(void) {
    cin >> n >> W;
    assert(2<=n&&n<=5000);
    assert(1<=W&&W<=n*1e12);
    rep(i, n) {
        P tmp; cin >> tmp.first >> tmp.second; assert(1<=tmp.first&&tmp.first<=1e12); assert(1<=tmp.first&&tmp.second<=1e12);
        if (tmp.second <= W) 
            ab.push_back(tmp);
    }
    n = ab.size();
    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];
        }
    }
    best_feasible_org = best_feasible;
    
    bitset<SIZE> b;
    cout << dfs(0, b, 0, 0) << endl;;
    if (best_feasible != best_feasible_org) {
//        return 1;
    }
//    assert(best_feasible == best_feasible_org);

    return 0;
}
0