• Source 
    1. /**************************************************************
    2. 	Problem: 1531
    3. 	User: zrts
    4. 	Language: C++
    5. 	Result: Accepted
    6. 	Time:348 ms
    7. 	Memory:964 kb
    8. ****************************************************************/
    9.  
    10. #include<cstdio>
    11. #include<cstring>
    12. #include<algorithm>
    13. //by zrt
    14. //problem:
    15. using namespace std;
    16. typedef long long ll;
    17. const double eps(1e-10);
    18. int n,b[205],c[205],K;
    19. int bag[40005];
    20. int main(){
    21. 	#ifdef LOCAL
    22. 	freopen("in.txt","r",stdin);
    23. 	freopen("out.txt","w",stdout);
    24. 	#endif
    25. 	bag[0]=1;
    26. 	scanf("%d",&n);
    27. 	for(int i=0;i<n;i++) scanf("%d",&b[i]);
    28. 	for(int i=0;i<n;i++) scanf("%d",&c[i]);
    29. 	scanf("%d",&K);
    30. 	int maxx=0;
    31. 	for(int i=0;i<n;i++){
    32. 		for(int j=1;j<=c[i];j<<=1){
    33. 			c[i]-=j;
    34. 			int w=j*b[i];
    35. 			for(int k=min(maxx,K-w);k>=0;k--){
    36. 				if(bag[k]){
    37. 					maxx=max(maxx,k+w);
    38. 					if(!bag[k+w]) bag[k+w]=bag[k]+j;
    39. 					else bag[k+w]=min(bag[k+w],bag[k]+j);
    40. 				}
    41. 			}
    42. 		}
    43. 		if(c[i]){
    44. 			int w=c[i]*b[i];
    45. 			for(int k=min(maxx,K-w);k>=0;k--){
    46. 				if(bag[k]){
    47. 					maxx=max(maxx,k+w);
    48. 					if(!bag[k+w]) bag[k+w]=bag[k]+c[i];
    49. 					else bag[k+w]=min(bag[k+w],bag[k]+c[i]);
    50. 				}
    51. 			}
    52. 		}
    53. 	}
    54. 	printf("%d\n",bag[K]-1);
    55. 	return 0;
    56. }