超大背包问题

问题描述：有重量和价值分别为w_i，v_i的n个物品，从这些物品中挑选总重量不超过W的物品，求所有挑选方案中，价值总和的最大值。
限制条件：
1≤n≤40
1≤w_i，v_i≤10¹⁵
1≤W≤10¹⁵
题解：如果用DP的话，复杂度是O(nW)，这里W数值非常大，所以不能用DP。挑选物品的方法总共有2ⁿ种，不能直接枚举，但可以像之前一样折半枚举，每部分20个是可行的，利用拆成两半后的两部分的价值和重量，可以求出原问题的解，我们把前半部分中的选取方法对应的重量和价值总和记为w1，v1，这样在后半部分寻找总重w2≤W-w1时使v2最大的选取方法就好了。接下来只要思考从枚举得到的(w2,v2)的集合中高效寻找max{v2|w2≤W'}的方法，首先，先排除所有w2[j]≥w2[i]而v2[j]≤v2[i]的所有j，这一点可以按照w2、v2的字典序排序后简单做到，此后剩余的元素都满足w2[i]<v2[j]⇿v2[i]<v2[j]，要计算max{v2|w2<W'}的话，只要寻找满足w2[i]≤W'的最大的i就可以了，这可以用二分来完成，剩余的元素个数为M的话，一次搜索需要O(logM)的时间，而M<2^(n/2)，所以总的时间复杂度是O(2^(n/2)n)。

代码：

 1 #include <cstdio>
 2 #include <cctype>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <utility>
 7 #define number s-'0'
 8 
 9 using namespace std;
10 
11 const int MAX_N=50;
12 const long long INF=0x3fffffffffffffff;
13 int n;
14 long long w[MAX_N], v[MAX_N];
15 long long W;
16 pair<long long, long long> ps[1<<(MAX_N/2)];
17 
18 void read(int &x){
19     char s;
20     x=0;
21     bool flag=0;
22     while(!isdigit(s=getchar()))
23         (s=='-')&&(flag=true);
24     for(x=number;isdigit(s=getchar());x=x*10+number);
25     (flag)&&(x=-x);
26 }
27 
28 void write(int x)
29 {
30     if(x<0)
31     {
32         putchar('-');
33         x=-x;
34     }
35     if(x>9)
36         write(x/10);
37     putchar(x%10+'0');
38 }
39 
40 long long max(long long x, long long y)
41 {
42     if (x>y) return x;
43     return y; 
44 }
45 
46 int main()
47 {
48     read(n);scanf("%I64d",&W);
49     for (int i=0; i<n; i++)
50     {
51         scanf("%I64d %I64d",&w[i], &v[i]);
52     }
53     int n2=n/2;
54     for (int i=0; i<1<<n2; i++)
55     {
56         long long sw=0, sv=0;
57         for (int j=0; j<n2; j++)
58         {
59             if (i>>j&1)
60             {
61                 sw+=w[j];
62                 sv+=v[j]; 
63             }
64         }
65         ps[i]=make_pair(sw, sv);
66     }
67     sort(ps, ps+(1<<n2));
68     int m=1;
69     for (int i=1; i<1<<n2; i++)
70     {
71         if (ps[m-1].second<ps[i].second)
72         {
73             ps[m++]=ps[i];
74         }
75     }
76     long long res=0;
77     for (int i=0; i<1<<(n-n2); i++)
78     {
79         long long sw=0, sv=0;
80         for (int j=0; j<n-n2; j++)
81         {
82             if (i>>j&1)
83             {
84                 sw+=w[n2+j];
85                 sv+=v[n2+j];
86             }
87         }
88         if (sw<=W)
89         {
90             long long tv=(lower_bound(ps, ps+m, make_pair(W-sw,INF))-1)->second;
91             res=max(res,sv+tv);
92         }
93     }
94     printf("%d
", res);
95 }