ZOJ 3631 Watashi's BG

Description

问题转化：

N个物品，重量等价于价值，背包承重W，求最大载重

1 <= N <= 40

0 <= M <= 1e7

w[i] <= 1e7

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4777 没找到合适的模板题

Idea

超大背包，折半枚举

2 ^ 40 ≈ 1e12,但折半后 2 ^ 20 ≈ 1e6,可枚举了

对前半部分枚举出所有方案，排序去除多余元素（重量大反而价值小，不针对此题），对后半部分的方案在枚举时二分搜索前半部分的方案，更新最佳答案

Code（Template）

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 2147483647;
const int N = 40;

int n, m;
ll w[N], v[N];
pair<ll, ll> p[1 << (N / 2)];

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        for(int i = 0; i < n; ++i)
            scanf("%lld", &w[i]), v[i] = w[i];

        //依次枚举前半部分方案
        int mid = n / 2;
        for(int i = 0; i < 1 << mid; ++i)
        {
            ll ww = 0, vv = 0;
            for(int j = 0; j < mid; ++j)
                if((i >> j) & 1)
                    ww += w[j], vv += v[j];
            p[i] = make_pair(ww, vv);
        }

        //去除多余元素
        sort(p, p + (1 << mid));
        int idx = 1;
        for(int i = 1; i < 1 << mid; ++i)
            if(p[idx - 1].second < p[i].second)
                p[idx++] = p[i];

        //枚举后半部分并二分搜索更新答案
        ll res = 0;
        for(int i = 0; i < 1 << (n - mid); ++i)
        {
            ll ww = 0, vv = 0;
            for(int j = 0; j < n - mid; ++j)
                if((i >> j) & 1)
                    ww += w[j + mid], vv += v[j + mid];
            if(ww <= m)
            {
                ll temv = (lower_bound(p, p + idx, make_pair(m - ww, INF)) - 1)->second;
                res = max(res, vv + temv);
            }
        }
        cout << res << '\n';
    }
}

枚举方案测试

for(int i = 0; i < (1 << n); ++i)
    {
        for(int j = 0; j < n; ++j)
            if(i >> j & 1)
                cout << j << ' ';
        cout << "\n-------------------------" << '\n';
    }