关键: 要使m最小,(m,b)中的数不能用(n,a)中的数表示出来
对于 3 19 10 6
19=10+3+3+3
6=3+3
只有3 和 10 不能被(n,a)中的数表示
所以m=2
只需要计算出存在多少个能被其它数组成的数计算出来就行了。
法一:完全背包
一个数只能被比它小的数字组成而不能被比它大的数字组成。
可以首先对数组排序,然后对于每一个数考虑能不能被它前面的数字所组成。
若x能够被前i个数组成,那么x-a[i]也能被前i个数组成
f[x]表示x能否被组成
则f [ x ] = f [ x ] | f [ x - a [ i ] ]
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int main()
{
int a[maxn];
int f[maxn];
int t,n;
int ans;
cin>>t;
while(t--){
memset(f,,sizeof(f));
cin>>n;
ans=n;
for(int i=;i<=n;i++)
cin>>a[i];
sort(a+,a+n+);
f[]=; //边界
for(int i=;i<=n;i++)
{
if(f[a[i]])//a[i]能被前面的数表示
{
ans--;
continue;
}
for(int j=a[i];j<=a[n];j++)
f[j]= (f[j]) | (f[j-a[i]]);
}
cout<<ans<<endl;
}
return ;
}