题意：

一个箱子，体积为N

两种宝物，体积为S1、S2，价值为V1、V2，数量无限

最多装多少价值的宝物

数据范围：2^32

 

完全背包？

NO NO NO

数据范围：2^32

 

分类枚举

如果s比较大，那么某一个最多装n/s个

如果s比较小，

s1个2，体积s1*s2，价值s1*v2

s2个1，体积s2*s1，价值s2*v1

如果s1*v2<s2*v1，那么2物品最多装s1-1个

#include
     
      #include
      
       using namespace std;typedef long long LL;int T;LL n,s1,v1,s2,v2;long long ans;int main(){    scanf("%d",&T);    for(int t=1;t<=T;t++)    {        scanf("%lld%lld%lld%lld%lld",&n,&s1,&v1,&s2,&v2);        ans=0;        if(s1>s2) swap(s1,s2),swap(v1,v2);        int maxn;        if(s2>n/s2) maxn=n/s2;        else        {            if(s1*v2>s2*v1) swap(s1,s2),swap(v1,v2);            maxn=s1-1;        }        for(int i=0;i<=maxn;i++) ans=max(ans,v2*i+(n-s2*i)/s1*v1);        printf("Case #%d: %lld\n",t,ans);    } }