此类问题通常一眼看上去像0-1背包问题，但是由于物品重量太大而超内存，往往不能采用DP而必须枚举。
问题1： （来自挑战程序设计）
有n个重量和价值分别为w[i]和v[i]的物品，从这些物品中挑选总重量不超过W的物品，求所有挑选方案中价值总和的最大值。其中，1 ≤ n ≤ 40， 1 ≤ w[i], v[i] ≤ 10^15, 1 ≤ W ≤ 10^15.
思路：
挑选物品的方案总共有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))，可以在实现内解决问题。
问题二：背包问题
（我是传送门）
01背包是是一个普通的动态规划入门问题：
一共有n个物品, 第i个物品的体积为v[i]；
有一个背包容量为m，现在我要挑选一些物品放入这个背包
我现在知道在总体积不超过背包容量的情况下,他一共有多少种放法(总体积为0也算一种放法)。
1 <= n <= 30, 1 <= m , v[i]<= 1e9
输入描述:
输入有多组，每一组第一行是n和m
接下来第二行到第n+1行，第i+1行表示v[i]。
输出描述:
输出每个样例的方案数，每个答案占据一行。
输入
3 10
1
2
4
输出
8
一看就是超内存，只能枚举，直接枚举的复杂度时候2^30≈1e9 会TLE，所以我们采用折半枚举的办法把枚举的复杂度降低一办，另一半就到前一半枚举出来的数组去找。 里面有一个知识点是二进制枚举集合（即用一个长为集合长的数来枚举整个集合第i为1表示取第i个，第i为为0表示不取第i个）
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
#define ULL unsigned long long
#define bug(x) cout<<"bug-----"<<x<<endl
#define R(i,n) for(int i = 0; i < n; i++)
using namespace std;
const int mod= 1e9+7;
const int maxn = 1e6 +10;
int a[maxn];
int main()
{
//freopen("C:\\Users\\admin\\Desktop\\1.in","r",stdin);
//freopen("C:\\Users\\admin\\Desktop\\1.out","w",stdout);
std::ios::sync_with_stdio(false);
int n,m;
while(cin>>n>>m)
{
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int t=n>>1;
int t2=n-t;
vector<LL> v;
int sum=0;
for(int i=0;i<1<<t;i++)
{
int ans=0;
for(int j=0;j<t;j++)
{
if(i&(1<<j))
{
ans+=a[j];
}
}
v.push_back(ans);
}
sort(v.begin(),v.end());
for(int i=0;i<1<<t2;i++)
{
int ans=0;
for(int j=0;j<t2;j++)
{
if(i&(1<<j))
{
ans+=a[t+j];
}
}
sum += lower_bound(v.begin(), v.end(), m - ans + 1) - v.begin();
}
cout<<sum<<endl;
}
return 0;
}