一些性质
1. a[i] 可以由 b[]表示
2. b[i] 不可以由 b[]/b[i]表示
3. b[i] 属于 a[]
1:
若(n,a) 和 (m,b) 等价,说明x要么可以同时让a[],b[]表示,要么就a[],b[]都不可以表示
显然a[i]一定可以被a[]表示
比如:a[i] = a[1] * t[1] + a[2] * t[2] + ... + a[n] * t[n],其中t[i] = 1,t[j] = 0,j!=i
那么a[i]一定可以被b[]表示
2:
如果b[i]可以由b[]/b[i]表示,那么说明b[i]是多余的,则说明(m,b)不是最小货币系统矛盾
3:
假设b[i]不属于a[]
由于b[i]可以由b[]表示,那么b[i]一定可以由a[]表示,那么b[i]是由a[]中哪些元素表示呢,
由于系数非负,b[i]又不属于a[],那么b[i]一定是由a[]中小于b[i]的元素a[j]组成的元素集合{a[j]}表示
由于a[j]可以由a[]表示,那么a[j]一定可以由b[]表示,那么a[j]是由b[]中哪些元素表示呢,
同理,一定是由b[]中小于a[j]的元素b[k]构成的集合{b[k]}表示
那么b[i]可以由小于b[i]的元素表示(因为b[i]>a[j]>b[k])
那么与第2条性质矛盾,所以b[i]属于a[]
算法
判断a[i]是否可以由其他元素表示,由于系数非负,如果a[i]可以由其他元素表示,一定是由比a[i]小的元素表示.
所以在判断a[i]是否可以由其他元素表示之前先对a[]进行从小到大排序
转化成a[i]能否由a[1]到a[i-1]组成,转化成完全背包问题
需要注意:a[i]能否由a[1]到a[i-1]组成这个事实是确定的,所以在背包问题推算过程中这个事实也是不会改变的
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
const int M = 25010;
int n,T,a[N],f[M];
/*TLE
int main(){
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);//从小到大排序
int res = 1;//a[1]一定不是多余的
for(int i=2;i<=n;i++){//判断a[i]是不是多余的
memset(f,0,sizeof(f));
f[0] = 1;
for(int j=1;j<=i-1;j++)
for(int k=a[j];k<=a[i];k++)
f[k] += f[k-a[j]];
if(!f[a[i]]) res++;//说明a[i]不可以由a[1]到a[i-1]表示所以a[i]不是多余的
}
cout<<res<<endl;
}
return 0;
}
*/
int main(){
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
memset(f,0,sizeof(f));
f[0] = 1;
int res = 0;
for(int i=1;i<=n;i++){
//注意判断语句的位置
if(!f[a[i]]) res++;
for(int j=a[i];j<=a[n];j++){
f[j] = f[j] | f[j-a[i]];
}
/*
不可以在这里判断这时候f[a[i]]表示f[i][a[i]]是前i件物品能否装满a[i]
我们希望判断是f[i-1][a[i]]
if(!f[a[i]]) res++;
*/
}
cout<<res<<endl;
}
return 0;
}