题目链接

思路：

 由于这个题目背包容量太大了，先不说会超时的问题，连dp数组都开不出来，所以我们要想办法减少背包容量，由此我们可以想到贪心。
 我们先按照密度最大到小对三个苹果进行排序，然后分出两个空间，一个较小的空间和一个较大的空间，较大的空间我们直接用密度最大的填满(也可能会剩一部分空间，就把剩下的自动分配给较小的空间)，然后对较小的部分进行完全背包，这样就解决了背包容量过大的问题
 但是要注意，利用贪心的时候，留出的这部分较小空间，不能太小
举个例子：
3个苹果；

4 7
3 5
6 2容量 6

显然我不考虑留空间大小，直接取最大密度苹果到不能取，剩下的空间进行背包
那么显然我应该取第一个苹果，价值为7
但是显然我取第二个苹果两次价值更高，所以一味的贪心是会出现错误的，我们必须要找到合适的空间进行完全背包，但是你问我怎么取较小的部分，目前我只能说靠猜(捂脸)，理论上是越大越好，但是考虑到时间复杂度，我取了一个1000

code

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxc = 1e4 + 5;
const int maxn = 4;struct Apple
{int val,weight;double p;//密度bool operator < (const Apple &a) const {return p > a.p;} 
}apple[maxn];int dp[maxc];int main()
{ios::sync_with_stdio(false);int t,k = 0;cin>>t;while(t--){memset(dp,0,sizeof dp);k++;for(int i = 1; i <= 3; i++){cin>>apple[i].weight>>apple[i].val;apple[i].p = 1.0 * apple[i].val / apple[i].weight;}sort(apple + 1,apple + 4);ll bag,ans = 0;cin>>bag;if(bag > 1000) ans = (bag - 1000) / apple[1].weight * apple[1].val,bag = 1000 + (bag - 1000) % apple[1].weight;for(int i = 1; i <= 3; i++){for(int j = apple[i].weight; j <= bag; j++){dp[j] = max(dp[j],dp[j - apple[i].weight] + apple[i].val); }}ans = ans + dp[bag];cout<<"Case "<<k<<": "<<ans<<endl;}return 0;
}