题目链接：https://uva.onlinejudge.org/external/123/12325.pdf
一开始是完全背包，那个容量是一个32位数字，存不下。
然后暴力枚举，当n很大，s1,s2很小的时候，是不行的。
然后一个一个枚举，竟然还是超时。
其实，当一个一个枚举的时候，可以这样想，当我的某一种比较小的时候就可以枚举他。
但是要是s1,s2都很小的时候，枚举哪个都是超时的。
这个时候，可以这样考虑，假设两中体积相等（1宝贝s2个，2宝贝s1个），但是他有一个性价比，价值分别是s2*v1 和 s1*v2;
那么如果1宝贝价值大一点，那么2宝贝肯定个数小于s1个，枚举这s1个就OK了
1 /* 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <iostream> 6 7 using namespace std; 8 9 int d[10000000]; 10 int s1,v1,s2,v2; 11 12 int dp(int s) { 13 int& ans = d[s]; 14 if(ans>=0) return ans; 15 ans = 0; 16 if(s-s1>=0)ans = max(ans,dp(s-s1)+v1); 17 if(s-s2>=0)ans = max(ans,dp(s-s2)+v2); 18 return ans; 19 } 20 21 22 int main() 23 { 24 int t; 25 cin>>t; 26 int kase = 1; 27 while(t--) { 28 memset(d,-1,sizeof(d)); 29 int s; 30 cin>>s; 31 cin>>s1>>v1>>s2>>v2; 32 int ans = dp(s); 33 printf("Case #%d: %d ",kase++,ans); 34 } 35 return 0; 36 } 37 */ 38 39 40 #include <cstdio> 41 #include <cstring> 42 #include <algorithm> 43 #include <iostream> 44 45 using namespace std; 46 47 #define INF 5000 48 49 int main() 50 { 51 52 int t; 53 cin>>t; 54 long long s,s1,v1,s2,v2; 55 int kase= 1; 56 while(t--) 57 { 58 long long ans = 0; 59 cin>>s>>s1>>v1>>s2>>v2; 60 61 if(s/s1<INF) 62 { 63 for(int i=0; i*s1<=s; i++) 64 { 65 ans = max(ans,(s-i*s1)/s2*v2+i*v1); 66 } 67 } 68 else if(s/s2<INF) 69 { 70 for(int i=0; i*s2<=s; i++) 71 { 72 ans = max(ans,(s-i*s2)/s1*v1+i*v2); 73 } 74 } 75 else { 76 long long sum1 = s2*v1; 77 long long sum2 = s1*v2; 78 if(sum1>sum2) { //1 de xing jia bi gao 79 for(long long i=0;i<s1;i++) 80 { 81 long long temp = s - i*s2; 82 ans = max(ans,temp/s1*v1+i*v2); 83 84 } 85 86 } 87 else { 88 for(long long i=0;i<s2;i++) { 89 long long temp = s - i*s1; 90 ans = max(ans,temp/s2*v2+i*v1); 91 } 92 } 93 } 94 printf("Case #%d: %lld ",kase++,ans); 95 } 96 return 0; 97 }