Description

有重量和价值分别为 w_i ( 1 ≤ w_i ≤ 10¹⁵ )、v_i ( 1 ≤ v_i ≤ 10¹⁵ ) 的 n (1 ≤ n ≤ 40 )个物品。从这些物品中挑选总重量不超过 C (1 ≤ C ≤ 10¹⁵)的物品，求所选挑选方案中价值总和的最大值。

Input

多测试用例。每个测试用例：

第一行是 n 和 C，接下来有 n 行，每行两个正整数，分别是各个物品的 w_i 和 v_i

Output

每个测试用例输出一行：最大价值。

Sample Input

4 5

2 3

1 2

3 4

2 2

Sample Output

7

 因为价值和重量都太过于大，数组是完全开不下了，不能记录状态，所以考虑其他方法。

如果是去暴力，那么就是暴力枚举物品的组合，然后找到一个组合使得价值最大，复杂度为 O( 2^n )

这里 max( n ) == 40 ，所以时间复杂度还是大到无法接受，考虑是否能将问题规模降下来。

考虑折半枚举法，假设现 n == 40，折半思想是先把前 2^20 个物品的组合先枚举预处理出来 2^20 个 w、v

然后如果我们能对于这枚举出来的前 2^20 个和后面 2^20 个物品的某个组合结合然后找出最优的结果

最后从这 2^20 个最优结果中再取最优就是答案，问题就是如何对于预处理出来的前 2^20 个组合与后面结合产生最优

假设现在背包容量为 C ，在前 2^20 个物品组合中取出一个，价值为 vi 重量为 wi 

那么如果我们能从后 2^20 个中找出一个组合使得其在满足重量 w' ≤ C - wi 的情况下价值最大

只要对于后 2^20 个的所有组合处理出其重量和价值，然后根据重量排序且根据价值去重

这样就能用二分查找来加快查找速度！

AC代码：

#include
       
        #define LL long longusing namespace std;const int maxn = 42;const LL INF = 0x3f3f3f3f;pair
        
          Pi[1<<(maxn/2)];LL W[maxn], V[maxn], C;int N;int main(void){    //freopen("in.txt", "r", stdin);    while(~scanf("%d %lld", &N, &C)){        for(int i=0; i
         
          >1;        for(int i=0; i<(1<
          
           > j & 1){                    SumW += W[j];                    SumV += V[j];                }            }            Pi[i] = make_pair(SumW, SumV);/// 将每个组合的 重量&&价值 用 pair 存起来        }        sort(Pi, Pi+(1<
           
            > j & 1){                    SumW += W[n+j];                    SumV += V[n+j];                }            }            if(SumW <= C){                int idx = (lower_bound(Pi, Pi+num, make_pair(C-SumW, INF)) - Pi)-1;                pair
            
              Temp = Pi[idx]; res = max(res, SumV + Temp.second); } } printf("%lld\n", res); } return 0;}