超大背包

题目描述

有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入描述

第一行为N$(1≤N≤40)$，V$(1≤V≤10^{15})$。

下面N行，第i行描述第i个物品的w[i]$(1≤w[i]≤10^{15})$，c[i]$(1≤c[i]≤10^{15})$，用一个空格分隔。

输出描述

输出只有一个数，最大总价值。

测试用例

输入

3 225274242
70498827 830583485
72910089 759360759
80945586 1095298545

输出

2685242789

输入

27 1405406868
500580317 1559925714
1191095816 2052289019
2086671060 125049457
1467200227 1826963529
1054830291 1055178046
457445390 293196664
1428828824 1163887408
27108927 353186119
354284919 1641947343
1044113045 1319050872
814300917 42212882
802287458 2142953934
1178508095 943859578
2133693898 163905627
1687820729 1091482274
737249638 2121489517
1203304272 1081378899
581034126 832395967
1370524005 487337507
178833685 1328104836
512934928 897959032
1629846549 1677014752
2011536830 64430283
547991487 1683026867
2125422226 728351378
744805340 261154211
1909716650 317131682

输出

5466192232

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, w[45], v[45], bw;
pair<ll, ll> ps[1 << (45 / 2)];  // 重量，价值

void solve() {
    // 枚举前半部分
    int n2 = n / 2;
    for (int i = 0; i < (1 << n2); ++i) {
        ll sw = 0, sv = 0;
        for (int j = 0; j < n2; ++j)
            if (i >> j & 1)
                sw += w[j], sv += v[j];
        ps[i] = {sw, sv};
    }
    // 去除多余的元素（去掉不是“物美价廉”的物品）
    sort(ps, ps + (1 << n2));
    int m = 1;
    for (int i = 1; i < (1 << n2); ++i)
        if (ps[m - 1].second < ps[i].second)
            ps[m++] = ps[i];
    // 枚举后半部分，并求解
    ll res = 0;
    for (int i = 0; i < (1 << (n - n2)); ++i) {
        ll sw = 0, sv = 0;
        for (int j = 0; j < (n - n2); ++j)
            if (i >> j & 1)
                sw += w[n2 + j], sv += v[n2 + j];
        if (sw < bw) {
            ll tv = (lower_bound(ps, ps + m, make_pair(bw - sw, LONG_LONG_MAX)) - 1)->second;
            res = max(res, sv + tv);
        }
    }
    printf("%lld", res);
}

int main() {
    cin >> n >> bw;
    for (int i = 0; i < n; ++i)
        scanf(" %lld%lld", &w[i], &v[i]);
    solve();
}