Description
有n种不同大小的数字，每种各个。判断是否可以从这些数字之中选出若干使它们的和恰好为K。
Input
首先是一个正整数T(1<=T<=100)
接下来是T组数据
每组数据第一行是一个正整数n(1<=n<=100)，表示有n种不同大小的数字
第二行是n个不同大小的正整数ai(1<=ai<=100000)
第三行是n个正整数mi(1<=mi<=100000)，表示每种数字有mi个
第四行是一个正整数K(1<=K<=100000)
Output
对于每组数据，如果能从这些数字中选出若干使它们的和恰好为K，则输出“Yes”，否则输出“No”，每个输出单独占一行
Sample Input
233 5 83 2 21721 21 14
Sample Output
Yes
No
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int n,k,a[1010][2],flag,v[1010];
void dfs(int sum)
{
int i,j;
if (flag==1){
return ;
}
if (sum > k){
return ;
}
if (sum == k){
flag = 1;
return ;
}
for (i=0; i<n; i++)
{
if (v[i] < a[i][1])
{
v[i]++;
dfs(sum+a[i][0]);
v[i]--;
}
}
}
int main()
{
int T,i,j;
cin>>T;
while (T--)
{
cin>>n;
for (i=0; i<n; i++){
cin>>a[i][0];
}
for (i=0; i<n; i++){
cin>>a[i][1];
}
cin>>k;
flag = 0;
memset(v, 0, sizeof(v));
dfs(0);
if (flag == 1){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
}
return 0;
}
