题目链接：

一开始是完全背包，那个容量是一个32位数字，存不下。

然后暴力枚举，当n很大，s1,s2很小的时候，是不行的。

然后一个一个枚举，竟然还是超时。

 

其实，当一个一个枚举的时候，可以这样想，当我的某一种比较小的时候就可以枚举他。

但是要是s1,s2都很小的时候，枚举哪个都是超时的。

这个时候，可以这样考虑，假设两中体积相等（1宝贝s2个，2宝贝s1个），但是他有一个性价比，价值分别是s2*v1 和 s1*v2;

那么如果1宝贝价值大一点，那么2宝贝肯定个数小于s1个，枚举这s1个就OK了

1 /* 2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           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\n",kase++,ans);34     }35     return 0;36 }37 */38 39 40 #include 
          
           41 #include 
           
            42 #include 
            
             43 #include 
             
              44 45 using namespace std;46 47 #define INF 500048 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
              
               sum2) { //1 de xing jia bi gao79 for(long long i=0;i