题目来自->P2347 砝码称重
题目描述 设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重≤1000），
输入格式 输入方式：a1,a2,a3, a4,a5 ,a6（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）
输出格式 输出方式：Total=N（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）
输入输出样例 输入
1 1 0 0 0 0
输出
Total=3
解法一： 01背包思想:记录0到1000重量是否成立，用1记录能称出的重量，0表示不能称出该重量。 用一个数组a记录所以砝码对应的重量。num记录砝码的个数。双重for循环遍历。 第一个for循环，依次用砝码
for (int i = 1;i <= num;i++) {//依次用砝码 }第二个for循环，从1000到0测试称重。（为什么从1000开始而不是从0开始？因为如果从0开始测试的话，当一个重量 j 可以称出时，此时用到的砝码a[i],那么重量（j + a[i])也可以测出，记录为1，那j++的话，当j = （j + a[i]) 时成立，则该砝码a[i]多次使用）
for (int j = 1000;j >= 0;j--) {//从最大重量称到0 if (f[j]) f[j + a[i]] = 1;//如果要称的重量前面可以称出来,则也可称出j+a[i]的重量 }解法一代码
#include <bits/stdc++.h> using namespace std; int b[7] = {0,1,2,3,5,10,20},a[1001]; int ans = 0,x,num; bool f[1001]; int main() { for (int i = 1;i <= 6;i++) { cin >> x;//砝码的数量 for (int j = 1;j <= x;j++) a[++num] = b[i];//存储每个砝码的质量 } f[0] = 1;//总重量为 0 即一个砝码也不用，我们将这种情况设为已有。 for (int i = 1;i <= num;i++)//依次用砝码 for (int j = 1000;j >= 0;j--) {//从最大重量称到0 if (f[j]) f[j + a[i]] = 1;//如果要称的重量前面可以称出来,则也可称出j+a[i]的重量 } for (int i = 1;i <= 1000;i++) if (f[i]) ans++; cout << "Total=" << ans; return 0; }解法二： 可用bitset快速解决这个问题 简单介绍下bitset C++的 bitset 在 bitset 头文件中，它是一种类似数组的结构，它的每一个元素只能是０或１，每个元素仅用１bit空间。其中封装了一堆奇奇怪怪操作并支持状态压缩的 bool 数组，而且支持基本的位运算 1.声明：
bitset<1001> s;
以上声明了长度为1001的bitset,并初始化为0; 2.本题核心操作：
例如 bits<4> s ;重量最大为4g,现在只有一个1g的砝码。 s[0] = 1；//0重量不需要砝码，这种情况设为1，此时s为0001 s |= s << 1；//左移1位0010,后与原来求并集得0011,这样就将1g重量设为了1
s.count()
返回s中1的个数，即为对应成立的重量个数。 以上介绍相信大家对bitset的操作以及了解 直接上代码：
#include <bits/stdc++.h> using namespace std; bitset<1001> s; int a[] = {1,2,3,5,10,20}; int main(){ int num; s[0] = 1; for(int i = 0;i < 6;i++){ cin >> num; for(int j = 0;j < num;j++) s |= s << a[i]; } cout << "Total="<< s.count() - 1;//减去0重量位置的1 return 0; }