hlg1201Zombie’s Treasure Chest---数学问题

Zombie’s Treasure Chest

Time Limit: 1000 MS

Memory Limit: 65536 K

Total Submit: 86(17 users)

Total Accepted: 16(13 users)

Rating:

Special Judge: No

Description

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

Source

2011 Asia Shanghai Regional Contest

Recommend

齐达拉图

题目大意：
只有两种物品的背包，每件物品有一定的价值和体积，可以无限取，问一个n的袋子最多能装多大的价值。

数量级为int

分析：
看到这个题我的第一反应是完全背包，然后试着做了一下，发现数组存不下，然后又找地推关系，枚举一遍又超时了===好悲催

这个题的第一反应应该是有一部分一定是装性价比高的剩下的装性价比低的

顺着这个思路，我们这么考虑，对于s1 s2的最小公倍数一定是s1，s2的整数倍那么全装性价比高的物品一定为最优解

也就是说对于最小公倍数的整数倍我们可以只装性价比高的物品而剩余的容量单独处理

但是这儿有一个问题便是剩余是多少；

可以这样考虑：剩余的体积一定是由小于1物品小于s1和2物品小于s2的部分组成的

剩余的体积必须完全包含这两部分才可以

即n%lcm+lcm 枚举即可

代码：

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 using namespace std;
 5 
 6 long long gcd(long long a,long long b)
 7 {
 8     while(b)
 9     {
10         long long c=a%b;
11         a=b;
12         b=c;
13     }
14     return a;
15 }
16 
17 long long get_gbs(long long a,long long b)
18 {
19     long long c=gcd(a,b);
20     return a/c*b;
21 }
22 
23 int main()
24 {
25     printf("%d
",5%3);
26     int t;
27     long long n,s1,s2,v1,v2,num,gbs,ans1,ans2,left,pre;
28     scanf("%d",&t);
29     for(int kase=1; kase<=t; kase++)
30     {
31         scanf("%lld %lld %lld %lld %lld",&n,&s1,&v1,&s2,&v2);
32         //if(s1<s2)
33         //{
34         //  swap(s1,s2);
35         // swap(v1,v2);
36         //}
37         gbs=get_gbs(s1,s2);
38         num=n/gbs;
39         if(num>1)
40         {
41             left=n%gbs+gbs;
42             pre=n-left;
43         }
44         else
45         {
46             pre=0;
47             left=n;
48         }
49         ans1=ans2=0;
50         if(v1*s2>v2*s1)
51             ans1=pre/s1*v1;
52         else
53             ans1=pre/s2*v2;
54         if(s1>=s2)
55         {
56             int xx=left/s1;
57             for(int i=0; i<=xx; i++)
58             {
59                 long long j=(left-s1*i)/s2;
60                 long long ss=v1*i+v2*j;
61                 if(ans2<ss)
62                     ans2=ss;
63             }
64         }
65         else
66         {
67             int xx=left/s2;
68             for(int i=0; i<=xx; i++)
69             {
70                 long long j=(left-s2*i)/s1;
71                 long long ss=v2*i+v1*j;
72                 if(ans2<ss)
73                     ans2=ss;
74             }
75         }
76         printf("Case #%d: %lld
",kase,ans1+ans2);
77     }
78     return 0;
79 }

View Code