dango

[hdu3236] Gift Hunting

（转自自己的CSDN博客）

一、题目描述

原题地址: http://acm.hdu.edu.cn/showproblem.php?pid=3236

GG有两张奖券，面额分别为V1、V2，准备给MM买礼物。当天是MM生日，所以MM还可以免费得到一份礼物。

礼物有价格和幸福值两个参数，并且礼物分为特殊礼物和普通礼物，特殊礼物是一定要全部到手的。

两张奖券不可以合并使用，、一种礼物也只能买一次。

问MM最大幸福值是多少，如果特殊礼物不能全部得到MM会不高兴，幸福值为-1。

二、题目分析

    比普通的二维背包问题多了两个设置，第一是MM可以免费得到一份礼物，第二是礼物分为特殊和普通两种。

1、特殊礼物是必买齐的，不管幸福值多少，所以要特殊处理一下。

2、用普通背包方法处理普通礼物。

3、由于还可以免费得到一份礼物，还需要一些小处理。

    用f[v1][v2][s]表示奖券V1,V2分别使用v1,v2时，且状态为s时候(s=1表示已经免费得到一份礼物了，s=0表示还木有免费得到礼物)，MM的幸福值。

    对于普通礼物，状态转移方程：

f[v1][v2][1] = max( f[v1][v2][1], f[v1][v2][0] + Normal[k].happiness )

f[v1][v2][0] = max( f[v1][v2][0], f[v1 - Normal[k].price][v2][0] + Normal[k].happiness, f[v1][v2 - Norma[k].price][0] + Normal[k].happiness)

    对于特殊礼物，就是直接往里头一个一个礼物塞了。

代码：

hdu3236
#include <cstdio>
#include <cstdlib>

int const MAXN = 300;

struct gift {
    int price, happiness;
} Special[MAXN],Normal[MAXN];

int V1, V2, Spe_Num, Nor_Num, Max_V1, Max_V2;
int f[500+100][50+10][2];    //f[v1][v2][s]奖券V1,V2用了v1 v2时的最大happy值，s=0表示还未使用Free 

bool Init();
bool Get_Special_Gift();     //fail --> return false;
int Get_Normal_Gift();

int main(){
    int T = 0;
    while (Init()){
        ++T;
        if (Get_Special_Gift())
            printf("Case %d: %d\n\n", T, Get_Normal_Gift());
        else
            printf("Case %d: -1\n\n", T);
    }
    return 0;
}

bool Init(){
    int n, i;
    
    scanf("%d%d%d", &V1, &V2, &n);
    if (V1 == 0 && V2 == 0 && n == 0) return false;

    Spe_Num = Nor_Num = 0;
    for (i = 0; i < n; i++) {
        int P, H, S;
        scanf("%d%d%d", &P, &H, &S);
        if (S == 1) {
            Special[Spe_Num].price = P;
            Special[Spe_Num++].happiness = H; 
        }
        else {
            Normal[Nor_Num].price = P;
            Normal[Nor_Num++].happiness = H;
        }
    }
    return true;
}
            
bool Get_Special_Gift(){
    int i,j,k,v1,v2,total, pre_total;
    bool flag;
    
    for (i = 0; i <= V1; i++)
        for (j = 0; j <= V2; j++)
            for (k = 0; k <= 1; k++) 
                f[i][j][k] = - 1;
    
    f[0][0][0] = total = 0;

    for (k=0; k<Spe_Num; k++)
    {
        pre_total = total;
        total += Special[k].happiness;
        for (v1=V1; v1>=0; v1--)
            for (v2=V2; v2>=0; v2--) {
                if (f[v1][v2][1] == pre_total)
                {
                    if (Special[k].price + v1 <= V1) f[Special[k].price + v1][v2][1] = total;
                    if (Special[k].price + v2 <= V2) f[v1][Special[k].price + v2][1] = total;
                }
                if (f[v1][v2][0] == pre_total)
                {
                    if (Special[k].price + v1 <= V1) f[Special[k].price + v1][v2][0] = total;
                    if (Special[k].price + v2 <= V2) f[v1][Special[k].price + v2][0] = total;
                    f[v1][v2][1] = total;
                }
            }
    }
    
    flag = false;

    for (i = 0; i <= V1; i++)
        for (j = 0; j <= V2; j++)
            for (k = 0; k <= 1; k++) {
                if (f[i][j][k] != total) f[i][j][k] = - 1;
                if (f[i][j][k] == total) flag =  true;
            }
                
    return flag;
}

int Get_Normal_Gift(){
    
    int v1,v2,s,k,ans = 0;
    
    for (k=0; k<Nor_Num; k++)
        for (v1 = V1; v1>=0; v1--)
            for (v2 = V2; v2>=0; v2--){
                for (s=0; s<=1; s++)
                    if (f[v1][v2][s] != -1){
                        if ( v1 + Normal[k].price<= V1 && f[v1][v2][s] + Normal[k].happiness > f[v1 + Normal[k].price][v2][s])
                            f[v1 + Normal[k].price][v2][s] = f[v1][v2][s] + Normal[k].happiness;
                        if ( v2 + Normal[k].price<= V2 && f[v1][v2][s] + Normal[k].happiness > f[v1][v2 + Normal[k].price][s])
                            f[v1][v2 + Normal[k].price][s] = f[v1][v2][s] + Normal[k].happiness;
                    }
                if (f[v1][v2][0] != -1 && f[v1][v2][0] + Normal[k].happiness > f[v1][v2][1])
                        f[v1][v2][1] = f[v1][v2][0] + Normal[k].happiness;
            }

    for (v1 = V1; v1 >= 0; v1--)
        for (v2 = V2; v2 >= 0; v2--)
            for (s=0; s<=1; s++)
                if (f[v1][v2][s] > ans) ans = f[v1][v2][s];
            
    return ans;
}

写在最后：

个人感觉这应该是非常经典非常基础的二维背包的一个小小拓展，思路上来说还是比较简单的，不过DP写起来还是有一些需要注意的，譬如初始化、边界判断、还有避免物品重复获得某些变量应该用downto而不是to。

还有可以优化之处，譬如v1和v2其实不需要都从V1、 V2开始逆循环，可以设置Max_V1, Max_V2表示截止到上一个礼物最多使用V1和V2中的多少，然后v1和v2从Max_V1, Max_V2开始循环到0。