用了排列的组合的方法,耗时比较长,差点没过,不过空间占用比较低。
按砝码种类的数量n递归,从第一个砝码种类开始,依次在该位置放【0,该种砝码数量】个数的砝码,递归,进入下一个位置的放置
边界条件:当递归进入了最后一个位置的下一位,即计算当前的和,压入set中


#include<iostream>
using namespace std;
#include<vector>
#include<set>


set<int> ans;
void findNum(vector<int> &weight,vector<int> &nums,vector<int> &tmp,int cur,int n)
{
    if(cur==n)
    {
        int ret=0;
        for(int i =0;i<n;i++)
        {
            ret+= weight[i]*tmp[i];
        }
        ans.insert(ret);
        
    }
    else
    {
        for(int i=0;i<=nums[cur];i++)
        {
             tmp[cur]=i;
             findNum(weight,nums,tmp,cur+1,n);
        }
    }
    return;
}


int main()
{
    int n ;
    while(cin>>n)
    {
        vector<int> weight(n);
        vector<int> nums(n);
        for(int i =0;i<n;i++)
        {
            cin>>weight[i];
        }
        //int sum=0;
        for(int i =0;i<n;i++)
        {
            cin>>nums[i];
            //sum+= nums[i]*weight[i];
        }
        vector<int> tmp(n,0);//临时存储各位置当前的个数
        findNum(weight,nums,tmp,0,n);
        cout<<ans.size()<<endl;
        ans.clear();
    }
    return 0;
}