首页 > ACM题库 > HDU-杭电 > HDU 4091-Zombie’s Treasure Chest-贪心-[解题报告]HOJ
2015
04-16

HDU 4091-Zombie’s Treasure Chest-贪心-[解题报告]HOJ

Zombie’s Treasure Chest

问题描述 :

  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.

输入:

  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.

输出:

  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.

样例输入:

2
100 1 1 2 2
100 34 34 5 3

样例输出:

Case #1: 100
Case #2: 86

题意:

输入背包体积n,绿宝石体积s1,价值v1,蓝宝石体积s2,价值v2,宝石数目无限,问背包里能放下的最大价值?

题解:

看过去很像完全背包,可数据很大(虽然没给出,也能猜到,不然太水了),所以不能用背包求。又只有两种物品,想到了贪心,将价值与体积比大(称为价值比)的优先放入。但体积限制,这样还不可以,还需要枚举减少价值比大的宝石个数,是否可以增大所求价值。又我们可以知道对于体积是m=lcm(s1,s2)背包,肯定全选价值比大的。所以至多只要枚举n-n/m+m的体积。如果小于这个值,存在大于m的空余,这个空余肯定用价值大的放置。

注意:

1.不够一个公倍数的时候,计算需要小心。。我就出错了。。

2.枚举的时候,跨度选择max(s1,s2),这个算是优化吧,没有的话会TLE

耗时:0MS/1000MS

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
typedef __int64 LL;
LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}
LL lcm(LL a,LL b)
{
    return a/gcd(a,b)*b;
}
int main()
{
    LL n,s1,v1,s2,v2;
    LL T,tt=0;
    cin>>T;
    while(T--)
    {
        LL i,j,k,ans,p,q,m,num;
        cin>>n>>s1>>v1>>s2>>v2;
        m=lcm(s1,s2);
        num=n/m;
        if(num){num--;}
        if(v1*s2>=v2*s1)
        {
            num=m/s1*num;
            p=(n-num*s1)/s2;
            ans=num*v1+p*v2;
            if(s1>=s2)
            {
                for(i=num;i*s1<=n;i++)
                {
                    q=i*v1+(n-i*s1)/s2*v2;
                    if(q>ans)ans=q;
                }
            }
            else
            {
                for(i=p;i>=0;i--)
                {
                    q=i*v2+(n-i*s2)/s1*v1;
                    if(q>ans)ans=q;
                }
            }
        }
        else
        {
            num=m/s2*num;
            p=(n-num*s2)/s1;
            ans=num*v2+p*v1;
            if(s2>=s1)
            {
                for(i=num;i*s2<=n;i++)
                {
                    q=i*v2+(n-i*s2)/s1*v1;
                    if(q>ans)ans=q;
                }
            }
            else
            {
                for(i=p;i>=0;i--)
                {
                    q=i*v1+(n-i*s1)/s2*v2;
                    if(q>ans)ans=q;
                }
            }
        }
        cout<<"Case #"<<++tt<<": "<<ans<<endl;
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/a601025382s/article/details/12308193


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.