首页 > ACM题库 > HDU-杭电 > HDU 3236-Gift Hunting-背包问题-[解题报告]HOJ
2014
03-09

HDU 3236-Gift Hunting-背包问题-[解题报告]HOJ

Gift Hunting

问题描述 :

After winning two coupons for the largest shopping mart in your city, you can’t wait inviting your girlfriend for gift hunting. Having inspected hundreds of kinds of souvenirs, toys and cosmetics, you finally narrowed down the candidate list to only n gifts, numbered 1 to n. Each gift has a happiness value that measures how happy your girlfriend would be, if you get this gift for her. Some of them are special – you must get it for your girlfriend (note that whether a gift is special has nothing to do with its happiness value).

Coupon 1 can be used to buy gifts with total price not greater than V1 (RMB). Like most other coupons, you can’t get any money back if the total price is strictly smaller than V1. Coupon 2 is almost the same, except that it’s worth V2. Coupons should be used separately. That means you cannot combine them into a super-coupon that’s worth V1+V2. You have to divide the gifts you choose into two part, one uses coupon 1, the other uses coupon 2.

It is your girlfriend’s birthday today. According to the rules of the mart, she can take one (only one) gift for FREE! Here comes your challenge: how to make your girlfriend as happy as possible?

输入:

There will be at most 20 test cases. Each case begins with 3 integers V1, V2 and n (1 <= V1 <= 500, 1 <= V2 <= 50, 1 <= n <= 300), the values of coupon 1 and coupon 2 respectively, and the number of candidate gifts. Each of the following n lines describes a gift with 3 integers: P, H and S, where P is the price, H is the happiness (1 <= P,H <= 1000), S=1 if and only if this is a special gift – you must buy it (or get it for free). Otherwise S=0. The last test case is followed by V1 = V2 = n = 0, which should not be processed.

输出:

There will be at most 20 test cases. Each case begins with 3 integers V1, V2 and n (1 <= V1 <= 500, 1 <= V2 <= 50, 1 <= n <= 300), the values of coupon 1 and coupon 2 respectively, and the number of candidate gifts. Each of the following n lines describes a gift with 3 integers: P, H and S, where P is the price, H is the happiness (1 <= P,H <= 1000), S=1 if and only if this is a special gift – you must buy it (or get it for free). Otherwise S=0. The last test case is followed by V1 = V2 = n = 0, which should not be processed.

样例输入:

3 2 4
3 10 1
2 10 0
5 100 0
5 80 0
3 2 4
3 10 1
2 10 0
5 100 0
5 80 1
0 0 0

样例输出:

Case 1: 120

Case 2: 100

#include<stdio.h>
#include<string.h>
#include<algorithm>
using std::sort;
#define inf -2100000000
#define MAXV1 501
#define MAXV2 51
#define MAXN 301
struct T
{
    int p,v,f;
    bool operator < (const T a) const
    {
        return f>a.f;
    }
} gift[MAXN];
int res[MAXV1][MAXV2][2];
inline int max (int a,int b,int c=0,int d=0)
{
    return (a>b?a:b)>(c>d?c:d)?(a>b?a:b):(c>d?c:d);
}
int main()
{
    int v1,v2,n,i,j,k,m,ts;
    int cas=1;
    while (scanf("%d%d%d",&v1,&v2,&n))
    {
        if (v1==0&&v2==0&&n==0) break;
        memset(res,0,sizeof(res));
        ts=0;
        for (i=1; i<=n; ++i)
        {
            scanf("%d%d%d",&gift[i].p,&gift[i].v,&gift[i].f);
            if (gift[i].f==1) ts+=gift[i].v;
        }
        sort(gift+1,gift+n+1);
        for (k=1; k<=n; ++k)
        {
            if (gift[k].f==0) break;
            for (i=v1; i>=0; --i)
            {
                for (j=v2; j>=0; --j)
                {
                    if (i>=gift[k].p&&j>=gift[k].p)
                    {
                        res[i][j][1]=max(res[i][j][0]+gift[k].v,res[i][j-gift[k].p][1]+gift[k].v,res[i-gift[k].p][j][1]+gift[k].v);
                        res[i][j][0]=max(res[i][j-gift[k].p][0]+gift[k].v,res[i-gift[k].p][j][0]+gift[k].v);
                    }
                    else if (i>=gift[k].p)
                    {
                        res[i][j][1]=max(res[i][j][0]+gift[k].v,res[i-gift[k].p][j][1]+gift[k].v);
                        res[i][j][0]=res[i-gift[k].p][j][0]+gift[k].v;
                    }
                    else if (j>=gift[k].p)
                    {
                        res[i][j][1]=max(res[i][j][0]+gift[k].v,res[i][j-gift[k].p][1]+gift[k].v);
                        res[i][j][0]=res[i][j-gift[k].p][0]+gift[k].v;
                    }
                    else
                    {
                        res[i][j][1]=res[i][j][0]+gift[k].v;
                    }
                }
            }
        }
        m=0;
        if (res[v1][v2][1]<ts&&res[v1][v2][0]<ts) m=-1;
        if (m==0)
        {
            for (; k<=n; ++k)
            {
                for (i=v1; i>=0; --i)
                {
                    for (j=v2; j>=0; --j)
                    {
                        if (res[i][j][0]>=ts) res[i][j][1]=max(res[i][j][1],res[i][j][0]+gift[k].v);
                        if (j>=gift[k].p&&res[i][j-gift[k].p][0]>=ts) res[i][j][0]=max(res[i][j-gift[k].p][0]+gift[k].v,res[i][j][0]);
                        if (i>=gift[k].p&&res[i-gift[k].p][j][0]>=ts) res[i][j][0]=max(res[i-gift[k].p][j][0]+gift[k].v,res[i][j][0]);
                        if (j>=gift[k].p&&res[i][j-gift[k].p][1]>=ts) res[i][j][1]=max(res[i][j-gift[k].p][1]+gift[k].v,res[i][j][1]);
                        if (i>=gift[k].p&&res[i-gift[k].p][j][1]>=ts) res[i][j][1]=max(res[i-gift[k].p][j][1]+gift[k].v,res[i][j][1]);
                    }
                }
            }
            for (i=1; i<=v1; ++i)
            {
                for (j=1; j<=v2; ++j)
                {
                    m=max(m,res[i][j][0],res[i][j][1]);
                }
            }
        }
        printf("Case %d: %d/n/n",cas++,m);
    }
    return 0;
}

参考:http://blog.csdn.net/acm_davidcn/article/details/5887392


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  3. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  4. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  5. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥