$x=a_1*t_1+a_2*t_2+a_3*t_3+…+a_n*t_n$(ti
非负)
性质:
$b_i$是从$a$中选的。
反证法:
若$b_i$不是$a$中的任一元素,那么$b_i$可以$a$中的元素被表示出来,就可以是$a_1*t_1+a_2*t_2+a_3*t_3$(一个例子),又因为a
与b
等价,所以$a_1*t1+a_2*t_2+a_3*t_3$也可以被表示为多个$b_j*t_j$的和,所以有$b_i=…+b_j*t_j+…$,既然$b_i$可以被b
中的其他元素所表示,那么b
也就没必要存在。如此往复,b
将为空! 所以$b_i$是从a
中选的。
知道了这一性质,我们就可以把搜索范围极大缩小,从所有非负整数缩小到n
,真是质的飞跃。
先把a
排好序,我们可以发现,只要$a_i$能被$a_1$~a i-1
中的数表示出来,$a_i$就不能存在,它多余了;$a_i$不能被$a_1$~a i-1
中的数表示出来,$a_i$就存在,维持a
与b
的等价关系。于是我们就可以发现,可以用完全背包问题来解决这个问题,背包体积就是$a_i$,$f[a_i]$就是总和恰好为$a_i$的方案数量。
#include<bits/stdc++.h>
using namespace std;
const int N = 110,M = 25010;
int f[M];//f[j]: 总和恰好为j的方案数
int a[N];
int n;
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);//元素排序
int m=a[n];
memset(f,0,sizeof f);
f[0]=1;
int res=0;//最小的m
for(int i=1;i<=n;i++)
{
if(!f[a[i]])res++;
for(int j=a[i];j<=m;j++)
f[j]+=f[j-a[i]];
//每个状态的转移,f[j]原等于不选a[i]的方案数,f[j-a[i]]是选a[i]的方案数
}
cout<<res<<endl;
}
}
收工!