题意：有重量和价值分别为wi，vi的n个物品。从这些物品中挑选总重量不超过W的物品，求全部挑选方案中价值总和的最大值。
限制条件：
1 <= n <= 40
1 <= wi, vi <= 10 的15次幂
1 <= W <= 10的15次幂
输入：
n = 4
w = {2, 1, 3, 2}
v = {3, 2, 4, 2}
W = 5
输出：
7（挑选0、1、3号物品）
分析：
这个问题是前面介绍过的背包问题，只是这次价值和重量都能够是很大的数值。相比之下n比較小。使用DP求解背包问题的复杂度是O(nW)。因此不能用来解决这里的问题。
我们能够向之前的题一样拆成两半之后再枚举。由于每部分仅仅有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就能够了。这能够用二分搜索完毕。
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 40 + 5;
const int INF = 10000000;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[i];sv += v[i];}}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);
}