1210: F.多重部分和问题
时间限制: 1 Sec 内存限制: 64 MB提交: 18 解决: 14
题目描述
有n种不同大小的数字，每种各个。判断是否可以从这些数字之中选出若干使它们的和恰好为K。
输入
首先是一个正整数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)
输出
对于每组数据，如果能从这些数字中选出若干使它们的和恰好为K，则输出“Yes”，否则输出“No”，每个输出单独占一行
样例输入
2
3
3 5 8
3 2 2
17
2
1 2
1 1
4
样例输出
Yes
No
一维多重背包二进制优化的思考：先看这个问题，100=1+2+4+8+16+32+37，观察可以得出100以内任何一个数都可以由以上7个数选择组合得到，所以对物品数目就不是从0都100遍历，而是0，1，2，4，8，16，32，37遍历，时间大大优化。
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 int main() 8 { 9 int T,n,k,count; 10 int a[101],b[101]; 11 int f[100001]; 12 int i,j,m,p,g; 13 cin>>T; 14 while(T--) 15 { 16 memset(f,0,sizeof(f)); 17 cin>>n; 18 for(i=1;i<=n;i++) 19 cin>>a[i]; 20 for(i=1;i<=n;i++) 21 cin>>b[i]; 22 cin>>k; 23 for(i=1;i<=n;i++) 24 { 25 p=0; 26 g=0; 27 while(b[i]>g) 28 { 29 for(j=k;j>=a[i]*g;j--) 30 { 31 f[j]=max(f[j],f[j-a[i]*g]+a[i]*g); 32 } 33 b[i]-=g; 34 g=pow(2,p); 35 p++; 36 } 37 for(j=k;j>=a[i]*b[i];--j) 38 { 39 f[j]=max(f[j],f[j-a[i]*b[i]]+a[i]*b[i]); 40 } 41 } 42 if(f[k]==k) 43 cout<<"Yes"<<endl; 44 else 45 cout<<"No"<<endl; 46 } 47 }
超时代码（未优化）
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 int main() 8 { 9 int T,n,k,count; 10 int a[101],b[101]; 11 int f[100001]; 12 int i,j,m; 13 int max; 14 cin>>T; 15 while(T--) 16 { 17 memset(f,0,sizeof(f)); 18 cin>>n; 19 for(i=1;i<=n;i++) 20 cin>>a[i]; 21 for(i=1;i<=n;i++) 22 cin>>b[i]; 23 cin>>k; 24 for(i=1;i<=n;i++) 25 { 26 for(j=0;j<=b[i];j++) 27 { 28 for(m=k;m>=a[i]*j;m--) 29 { 30 if(f[m]<(f[m-j*a[i]]+j*a[i])) 31 f[m]=f[m-j*a[i]]+j*a[i]; 32 } 33 } 34 } 35 cout<<f[k]<<endl; 36 if(f[k]==k) 37 cout<<"Yes"<<endl; 38 else 39 cout<<"No"<<endl; 40 } 41 }