题解 | #称砝码#
称砝码
http://www.nowcoder.com/practice/f9a4c19050fc477e9e27eb75f3bfd49c
用了排列的组合的方法，耗时比较长，差点没过，不过空间占用比较低。
按砝码种类的数量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;
}
