给一个背包的容量n，两种物品的花费a,c和价值b,d，问最多能装多少价值。
分析：就是n/(a*c/gcd(a,c))-1个a，c的最小公倍数的背包容量肯定是装相对价值比较大的那个物品，剩下的对花费较大的那个物品进行枚举，求出剩下的能装的最大价值
#include"stdio.h"
#include"string.h"
#define max(a,b) a>b?a:b
__int64 fun(__int64 a,__int64 b)
{
__int64 c,d=1;
if(a<b)
{
c=a;
a=b;
b=c;
}
while(d>0)
{
d=a%b;
a=b;
b=d;
}
return a;
}
int main()
{
__int64 s,s1,s2,v1,v2,n,m,tmp,res,t,max;
int k,i,r=1;
scanf("%d",&k);
while(k--)
{
scanf("%I64d%I64d%I64d%I64d%I64d",&s,&s1,&v1,&s2,&v2);
tmp=s1/fun(s1,s2)*s2;
n=s/tmp,m=s%tmp;
if(n)
{
n--;
m+=tmp;
}
res=max(n*(tmp/s1)*v1,n*(tmp/s2)*v2);
if(s1<s2)
{
t=s1;s1=s2;s2=t;
t=v1;v1=v2;v2=t;
}
max=0;
for(i=0;i<=m/s1;i++)
{
t=i*v1+(m-i*s1)/s2*v2;
if(max<t)
max=t;
}
printf("Case #%d: %I64d\n",r++,max+res);
}
return 0;
}