Some brave warriors come to a lost village. They are very lucky and find a lot of treasures and a big treasure chest, but with angry zombies. The warriors are so brave that they decide to defeat the zombies and then bring all the treasures back. A brutal long-drawn-out battle lasts from morning to night and the warriors find the zombies are undead and invincible. Of course, the treasures should not be left here. Unfortunately, the warriors cannot carry all the treasures by the treasure chest due to the limitation of the capacity of the chest. Indeed, there are only two types of treasures: emerald and sapphire. All of the emeralds are equal in size and value, and with infinite quantities. So are sapphires. Being the priest of the warriors with the magic artifact: computer, and given the size of the chest, the value and size of each types of gem, you should compute the maximum value of treasures our warriors could bring back. Input There are multiple test cases. The number of test cases T (T ≤ 200) is given in the first line of the input file. For each test case, there is only one line containing five integers N, S1, V1, S2, V2, denoting the size of the treasure chest is N and the size and value of an emerald is S1 and V1, size and value of a sapphire is S2, V2. All integers are positive and fit in 32-bit signed integers. Output For each test case, output a single line containing the case number and the maximum total value of all items that the warriors can carry with the chest. Sample Input 2 100 1 1 2 2 100 34 34 5 3 Sample Output Case #1: 100 Case #2: 86 题目大意： 给你一个n体积的背包，以及两种无限多的物品， 体积价值分别是s1 v1 s2 v2 都是32位整数，问怎样选取 使得总价值最大 题目分析： 就是贪心喽，就是想一下枚举策略，显然传统的背包问题内存肯定不够
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define LL long long int main(int argc,char* argv[]) { int t,kase = 0; LL n,s1,s2,v1,v2; LL Ans = 0; scanf("%d",&t); while(t--) { scanf("%d",&n); scanf("%lld %lld %lld %lld",&s1,&v1,&s2,&v2); Ans = 0; if(s1 > s2) { swap(s1,s2); swap(v2,v1); }// 这样肯定是s2 的体积更大一点 if(n / s2 > 65536) { // 除数比较大 说明s1 s2都比较小 // 那么就是存在一个性价比 假设2的性价比小 那么2的数量一定小于s1 个 否则放个v1更加优秀 ( // 2物品的体积一定也大于等于1 假如选了s1个2物品 一定是能放开一个1物品的) for(int i=0; i<=s1; i++) Ans = max(Ans,v2 * i + (n - s2 * i ) / s1 * v1); for(int i=0; i<=s2; i++) Ans = max(Ans ,v1 * i + (n - s1 * i) / s2 * v2); } else { for(int i=0; i<=n/s2; i++) Ans = max(Ans,i * v2 + (n - i * s2) / s1 * v1); } printf("Case #%d: %lld\n",++kase,Ans); } return 0; }