結果

問題 No.626 Randomized 01 Knapsack
ユーザー tsutajtsutaj
提出日時 2017-12-19 19:28:28
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 550 ms / 2,000 ms
コード長 2,639 bytes
コンパイル時間 727 ms
コンパイル使用メモリ 73,728 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-08 10:09:13
合計ジャッジ時間 5,802 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,384 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 4 ms
4,376 KB
testcase_07 AC 13 ms
4,384 KB
testcase_08 AC 6 ms
4,376 KB
testcase_09 AC 37 ms
4,380 KB
testcase_10 AC 14 ms
4,376 KB
testcase_11 AC 86 ms
4,376 KB
testcase_12 AC 306 ms
4,376 KB
testcase_13 AC 212 ms
4,376 KB
testcase_14 AC 74 ms
4,376 KB
testcase_15 AC 224 ms
4,380 KB
testcase_16 AC 293 ms
4,376 KB
testcase_17 AC 244 ms
4,380 KB
testcase_18 AC 214 ms
4,380 KB
testcase_19 AC 283 ms
4,376 KB
testcase_20 AC 456 ms
4,376 KB
testcase_21 AC 282 ms
4,380 KB
testcase_22 AC 498 ms
4,380 KB
testcase_23 AC 550 ms
4,376 KB
testcase_24 AC 73 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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