题解、自码代码待编辑

上标程

#include <cstdio>
#include <iostream>
#include <algorithm>
#define MAX_N 40
using namespace std;
long long INF = 0x3F3F3F3F3F3F3F3FLL;   //设为 (1<<20) 也可以
pair< long long, long long > ps[1 << (MAX_N / 2)];   //(重量，价值)

int main()
{
    long long w[MAX_N], v[MAX_N];
    long long N, W;
    
    
    freopen("knapsack.in","r",stdin);
    freopen("knapsack.out","w",stdout);
    scanf("%lld %lld", &N, &W);
    for (int i = 0; i < N; i++)
        scanf("%lld %lld", &v[i], &w[i]);
         
    //枚举前半部分 O(2^N/2)
    int N2 = N / 2;
    for (int i = 0; i < 1 << N2; i++)
    {
        long long sw = 0LL, sv = 0LL;
        for (int j = 0; j < N2; j++)
        {
            if (i >> j & 1)
            {
                sw += w[j];
                sv += v[j];
            }
        }
        ps[i] = make_pair(sw, sv);
    }
    
    //去除多余的元素： sw[i] <= sw[j] 并且 sv[i] >= sv[j] 
    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];
    
    //枚举后半部分 O(2^N/2)并求解
    long long res = 0LL;
    for (int i = 0; i < 1 << (N - N2); i++)
    {
        long long sw = 0LL, sv = 0LL;
        for (int j = 0; j < N - N2; j++)
        {
            if (i >> j & 1)
            {
                sw += w[N2 + j];
                sv += v[N2 + j];
            }
        }
        if (sw <= W)
        {
            long long tv = (lower_bound(ps, ps + m, make_pair(W - sw, INF)) - 1) -> second;
            res = max(res, sv + tv);
        }
    }
    printf("%lld\n", res);
    fclose(stdin);
    fclose(stdout); 
     
    return 0; 
}