题意: 现有 (n) 个砝码，重量分别为 (a_i) ，在去掉 (m) 个砝码后，问最多能称量出多少不同的重量（不包括 (0)）。 请注意，砝码只能放在其中一边。
(nleq20,mleq 4,m<n,a_ileq 100)
题目分析: 看到 (n,m) 的范围果断爆搜/状压，而对于当前的状态，计算称量出有多少种重量实际为01背包问题，也就是枚举到一个状态后01背包。
这里01背包我用了bitset优化，时间复杂度默认为 (mathcal{O}(frac{n}{w})) （具体含义见 wiki )
算法一: 迭代加深搜索+记忆化 (mathcal{O}(C_n^mnfrac{sum a_i}{w})))
考虑枚举去掉哪个砝码，也就是 (m) 个 (n) 为上界的 for 循环，但是这里 (m) 是给定的，可以进行迭代加深搜索。
记录 (now) 为当前状压的状态， (h) 为删掉了几个数，如果 (h) 为 (0) 就01背包，否则找到一个没有删掉的砝码，删掉并且往下搜索，假设删掉了(i)，则有 (now) 中把 (i) 标记,(h) 变成 (h-1) 后继续搜索。
核心代码:
int a[N];
bool f[1050000];
std::bitset<20010>vis;
void dfs(int now, int h) {
if(f[now]) return ;
f[now] = 1;
if(h == 0) {
vis.reset();
vis |= 1;//空位一种可以转移走的状态
for(int i = 1; i <= n; ++i) {
if((1 << i - 1) & now)
vis |= vis << a[i];
}
ans = Max(ans, vis.count() - 1);//去掉空的状态，所以要-1
}
else {
for(int i = 1; i <= n; ++i)
if((1 << i - 1) & now)
dfs(now - (1 << i - 1), h - 1);
}
}
算法二: 状压 (mathcal{O}(C_n^mnfrac{sum a_i}{w}))
枚举每一种选的状态（不管合不合法），通过计算该状态中 (1) 的数量（也就是砝码的数量）来判断合不合法，如果合法就01背包计算。
核心代码
inline int lowbit(int x) { return x & (-x); }//最后一位二进制数
bool check(int x) {//判断是否有n-m个1
int cnt = 0;
while(x) {
++cnt;
x -= lowbit(x);
if(cnt > n - m) return 0;
}
return cnt == n - m;
}
int main() {
n = read(); m = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 0; i <= (1 << n) - 1; ++i) {
if(!check(i)) continue;
vis &= 0; vis |= 1;
for(int j = 1; j <= n; ++j)
if(i & (1 << j - 1))
vis |= vis << a[j];
ans = Max(ans, vis.count() - 1);
}
printf("%d
", ans);
return 0;
}