【题意】

有n个重量和价值分别为w[i]和v[i]的物品，从这些物品中挑选总重量不超过W的物品，求所有挑选方案中价值总和的最大值。其中，1 ≤ n ≤ 40， 1 ≤ w[i], v[i] ≤ 10^15, 1 ≤ W ≤ 10^15.

【解题思路】

这个问题给人的第一感觉就是普通的01背包。不过，看完数据范围会发现，这次价值和重量都可以是非常大的数值，相比之下n比较小。使用DP求解背包为题的复杂度是O(nW)，因此不能用来解决这个问题。此时我们应该利用n比较小的特点来寻找其他方法。

挑选物品的方案总共有2^n种，所以不能直接枚举，但是如果将物品分成两半再枚举的话，由于每部分最多只有20个，这是可行的。我们把前半部分中的挑选方法对应的重量和价值总和记为w1、v1，这样在后半部分寻找总重w2 ≤ W - w1时使v2最大的选取方法即可。

因此，我们要思考从枚举得到的（w2，v2）集合中高效寻找max{v2|w2 ≤ W'}的方法。首先，显然我们可以排除所有w2[i] ≤ w2[j] 并且 v2[i] >= v2[j]的j。这一点可以按照w2、v2的字典序排序后做到。此后剩余的元素都满足w2[i] < w2[j] <=> v2[i] < v2[j]，要计算max{v2|w2 <= W'}的话，只要寻找满足w2[i] <= W'的最大的i就可以了。这可以用二分搜索完成，剩余的元素个数为M的话，一次搜索需要O(logM)的时间。因为M≤2^(n/2)，所以这个算法总的时间复杂度是O(n * 2^(n/2))，可以在实现内解决问题。

【AC code】 
//超大背包问题
//样例:
//n=4
//w={2,1,3,2}
//v={3,2,4,2}
//W=5
//ans=7(choose 0,1,3 object)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const ll inf=1e18;
const int maxn=40;
int n;
ll w[maxn],v[maxn];
ll W;
pair<ll,ll>ps[1<<(maxn/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]=make_pair(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<=W){
            ll tv=(lower_bound(ps,ps+m,make_pair(W-sw,inf))-1)->second;
            res = max(res,sv+tv);
        }
    }
    printf("%lld\n",res);
}
int main()
{
    cin>>n;
    for(int i=0; i<n; i++) cin>>w[i];
    for(int i=0; i<n; i++) cin>>v[i];
    cin>>W;
    solve();
    return 0;
}