三维动态规划 hdu 4501 小明系列故事——买年货

3维动态规划 hdu 4501 小明系列故事——买年货

 

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4501

 

题目大意：

一共有n件商品，每件商品有一个购买价钱，购买积分，得分价值。

现有k件物品的选购机会，有v1元钱，v2积分，问能获得的最大得分价值是多少。

 

解题思路：

dp[i][j][k]表示有i元钱，j积分和k个免费商品的机会，能获得的最大的得分价值。

对每件商品一共有四种选择，1、用钱买 2、用积分换 3、用一个免费商品的名额 4、什么都不用

 

代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#define eps 1e-6
#define INF (1<<20)
#define PI acos(-1.0)
using namespace std;

int dp[110][110][10];  //dp[i][j][k]表示有i人民币，j积分,k次免费的机会能够获得的最大价值

struct Thing
{
    int a,b,val;
}thing[110];



int main()
{
    int n,v1,v2,k;

    while(scanf("%d%d%d%d",&n,&v1,&v2,&k)!=EOF)
    {
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&thing[i].a,&thing[i].b,&thing[i].val);
            sum+=thing[i].val;
        }

        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            for(int q=k;q>=0;q--)
            for(int j=v1;j>=0;j--)
                for(int p=v2;p>=0;p--)
                    {
                        if(j>=thing[i].a&&p>=thing[i].b) //如果能够用积分或钱
                        {
                            dp[j][p][q]=max(max(dp[j-thing[i].a][p][q]+thing[i].val,dp[j][p-thing[i].b][q]+thing[i].val),dp[j][p][q]);
                            if(q>=1)  //如果能用免费的名额
                                dp[j][p][q]=max(dp[j][p][q],dp[j][p][q-1]+thing[i].val);
                        }
                        else if(j<thing[i].a&&p<thing[i].b) //如果钱和积分都不能用
                        {
                            if(q>=1)
                                dp[j][p][q]=max(dp[j][p][q],dp[j][p][q-1]+thing[i].val);
                        }
                        else if(j<thing[i].a) //只能用积分
                        {
                            dp[j][p][q]=max(dp[j][p-thing[i].b][q]+thing[i].val,dp[j][p][q]);
                            if(q>=1)
                                dp[j][p][q]=max(dp[j][p][q],dp[j][p][q-1]+thing[i].val);
                        }
                        else   //只能用钱
                        {
                            dp[j][p][q]=max(dp[j-thing[i].a][p][q]+thing[i].val,dp[j][p][q]);
                            if(q>=1)
                                dp[j][p][q]=max(dp[j][p][q],dp[j][p][q-1]+thing[i].val);
                        }

                    }
            printf("%d\n",dp[v1][v2][k]);


    }

    return 0;
}