题目如下：

以前，有个神秘的院子里面有三种苹果，每个苹果的数量是无限的。有一个小姑娘带了一个大袋子来到院子，她从来没见过这么多的苹果。每种苹果都有大小以及出售的价格，小姑娘想获得最大的利润，但是她不知道怎么才能做到。于是她来向你寻求帮助，你能告诉她能获得的最大价值吗？

第一行一个整数T(T <= 50)，表示测试数据的组数。
每组测试数据有四行组成，前三行每行有两个整数S和P，分别表示每种苹果的大小(1 <= S <= 100)和价格(1 <= P <= 10000)
第四行有一个整数V(1 <= V <= 100,000,000)表示小姑娘袋子的大小。

刚看到这个题以为是完全背包，但是看完数据量之后看到背包大小为100000000，所以这个题肯定是不止要用完全背包就可以解决。然后就行到了贪心方法，先将大部分背包用性价比最高的方式填满，然后剩下的在使用完全背包求取最优值，此时的计算结果就可以将背包的价值最大化。

#include<iostream>
using namespace std;
#define ll long long
#include<algorithm>
#include<cstring>struct node
{ll x,y;double z;bool operator<(const node &q) const{return z>q.z;}
} a[4];
ll dp[1001];
int main()
{ll t;cin>>t;for(ll o=1; o<=t; o++){memset(dp,0,sizeof dp);for(int i=1; i<=3; i++){cin>>a[i].x>>a[i].y;a[i].z=(double)((double)a[i].y/(double)a[i].x);}sort(a+1,a+4);ll sum=0;ll bag;cin>>bag;if(bag>1000){sum+=((bag-1000)/a[1].x+1)*a[1].y;bag-=((bag-1000)/a[1].x+1)*a[1].x;}for(int i=1; i<=3; i++)for(int j=a[i].x; j<=bag; j++)dp[j]=max(dp[j],dp[j-a[i].x]+a[i].y);cout<<"Case "<<o<<": "<<sum+dp[bag]<<endl;}
}