题解 | #称砝码#

#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
//高中数学计数原理
// 1. 元素个数为n的集合有2^n次方个子集，相当于若是可重复的那么会组合出2^n种重量
// 2. 将砝码依次加入集合，用递归思想解决
// 3. 如有三个不同重量的砝码为1，2， 3，把整个过程看成是二叉树的层次结构
//     3.1 一开始都不选则集合为        {0}, 
//     3.2 到1，可选可不选           {0， 1}
//     3.3 轮到2，可选可不选        {0，2}{1，3}
//     3.3 轮到3                  0,3 2,5 1,4 3,6 要去重相当于二叉树剪枝干，把一个3去掉就好

int main() {
    
    int n = 0;
    vector<int> weights;
    vector<int> num;

    cin >> n;
    int temp = 0;
    for(int i = 0; i != n; ++ i)
    {
        cin >> temp;
        weights.push_back(temp);
    }
    for(int i = 0; i != n; ++ i)
    {
        cin >> temp;
        num.push_back(temp);
    }

    //得到全部砝码
    vector<int> all_wights;
    for(int i = 0; i != n; ++ i)
    {
        for(int j = 0; j < num[i]; ++j)
        {
            all_wights.push_back(weights[i]);
        }
    }

    set<int> diff_weight;
    diff_weight.insert(0);
    for(int i = 0; i < all_wights.size(); ++i)
    {
        set<int> tmpset(diff_weight);
        for(auto iter = tmpset.begin(); iter != tmpset.end(); ++ iter)
        {
            diff_weight.insert(*iter + all_wights[i]);
        }
    }

    cout << diff_weight.size();


}
// 64 位输出请用 printf("%lld")