题目描述
现有n个砝码，重量分别为 a_ia**i，在去掉 mm 个砝码后，问最多能称量出多少不同的重量（不包括 00）。
请注意，砝码只能放在其中一边。
输入格式
第 11 行为有两个整数 nn 和 mm，用空格分隔。
第 22 行有 nn 个正整数 a_1, a_2, a_3,ldots , a_na1,a2,a3,…,a**n，表示每个砝码的重量。
输出格式
仅包括 11 个整数，为最多能称量出的重量数量。
输入输出样例
输入 #1复制
3 1
1 2 2
输出 #1复制
3
由于n和m都比较小，考虑状压，第一重循环枚举状态，即
for(int i = 0; i < (1 << n); i++)
然后判断一下如果这种状态（i的二进制表示）有n - m个1，说明是合法的，可以计算这种状态下的砝码最多能构成多少种不同的重量。
用到的bitset可以看成是定长的bool数组，不过有很多自带的成员函数。b[i] = 1表示重量i可以被称出，一开始初始化b[0] = 1表示重量0可以被称出，这也是为了后续的计算。
然后就是遍历一遍重量数组，比较关键的两行是：
if(i & (1 << j))//如果i的第j位上是1
b = b | b << a[j];
把b看作一个集合，或运算就相当于集合合并，如果i的第j位上是1，说明这种状态下第j个物品可选可不选，那么不选自然对应原来的b（不变），选的话就让b左移a[j]位这样原来的第i位如果为1，现在第i + a[j]为就是1（代表重量i+a[j]可以被称出来），这两种情况或起来就是新的集合了。最后用b.count()统计b里1的个数更新答案。
注意最终要把答案减1（重量为0实际上不可以被称出来）。
#include <iostream>
#include <bitset>
using namespace std;
int n, m, a[25], ans = 0;
int count(int x)
{
int cnt = 0;
for (int i = 0; i < n; i++)
{
if(x & (1 << i))
cnt++;
}
return cnt;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < (1 << n); i++)
{
if(count(i) == n - m)
{
bitset<2005> b;
b[0] = 1;//重量为0的可以被称出
for (int j = 0; j < n; ++j)
{
if(i & (1 << j))
b = b | b << a[j];
}
ans = max(ans, (int)b.count());
}
}
cout << ans - 1;
return 0;
}