結果

問題 No.626 Randomized 01 Knapsack
コンテスト
ユーザー tsutaj
提出日時 2017-12-19 19:28:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 533 ms / 2,000 ms
コード長 2,639 bytes
コンパイル時間 771 ms
コンパイル使用メモリ 74,652 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 03:30:26
合計ジャッジ時間 5,429 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bitset>
#include <iostream>
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pll;
const ll INF = 1LL << 60;
const int SIZE = 5010;

ll N, W;
ll best_feasible = -INF;

// value, weight
pll elem[SIZE];
ll v[SIZE], w[SIZE];

// 線形緩和問題 (離散的ではなく、連続なものを扱う)
// idx 未満まではどう選んだかが確定していて、idx 以降は未確定
pair<double, bool> Relaxation(int idx, const bitset<SIZE> &b) {
    double ans = 0;
    double cur_w = W;
    for(int j=0; j<idx; j++) {
        ans += b[j] * v[j];
        cur_w -= b[j] * w[j];
    }

    // 元問題の制約を厳密に満たすか？
    // 取るか取らないかなので、本来なら 0 減るか w[j] 減るかするはず
    // 整数値に限らないなら (緩和)、比が大きいものから貪欲に取り続けるのが最適！！
    bool ret = true;
    for(int j=idx; j<N; j++) {
        double tmp = min<double>(cur_w, w[j]);
        ret &= (tmp == 0 || tmp == w[j]);
        cur_w -= tmp;
        ans += tmp * (v[j] * 1.0 / w[j]);
    }
    return make_pair(ans, ret);
}

ll dfs(int idx, bitset<SIZE> &b, ll cur_v, ll cur_w) {
    if(idx == N) {
        best_feasible = max(best_feasible, cur_v);
        return cur_v;
    }
    
    auto relax_p = Relaxation(idx, b);
    double relax = relax_p.first;
    bool   satis = relax_p.second;

    // 元の制約を満たしているなら、それが最適になるかも
    if(satis) {
        best_feasible = max<ll>(best_feasible, relax);
        return relax;
    }

    // 緩和して貪欲に取ったのに許容解より低い → どうやっても更新できないので抜けよう
    if(relax < best_feasible) {
        return -INF;
    }

    ll tmp = -INF;

    // i 番目を取る
    if(cur_w + w[idx] <= W) {
        b[idx] = 1;
        tmp = max(tmp, dfs(idx+1, b, cur_v + v[idx], cur_w + w[idx]));
        b[idx] = 0;
        best_feasible = max(best_feasible, tmp);
    }

    // i 番目を取らない
    tmp = max(tmp, dfs(idx+1, b, cur_v, cur_w));
    best_feasible = max(best_feasible, tmp);
    return tmp;
}

int main() {
    scanf("%lld%lld", &N, &W);
    for(int i=0; i<N; i++) {
        scanf("%lld%lld", &elem[i].first, &elem[i].second);
    }

    sort(elem, elem+N, [&](pll a, pll b) {
        return a.first * b.second > a.second * b.first;
    });

    for(int i=0; i<N; i++) {
        v[i] = elem[i].first;
        w[i] = elem[i].second;
    }

    bitset<SIZE> b;
    dfs(0, b, 0, 0);
    printf("%lld\n", best_feasible);
    return 0;
}
0