首页 > 代码库 > HDU 3182 Hamburger Magi（状压dp）

HDU 3182 Hamburger Magi（状压dp）

2024-07-31 23:30:28   220人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3182


Problem Description
In the mysterious forest, there is a group of Magi. Most of them like to eat human beings, so they are called “The Ogre Magi”, but there is an special one whose favorite food is hamburger, having been jeered by the others as “The Hamburger Magi”.
Let’s give The Hamburger Magi a nickname “HamMagi”, HamMagi don’t only love to eat but also to make hamburgers, he makes N hamburgers, and he gives these each hamburger a value as Vi, and each will cost him Ei energy, (He can use in total M energy each day). In addition, some hamburgers can’t be made directly, for example, HamMagi can make a “Big Mac” only if “New Orleams roasted burger combo” and “Mexican twister combo” are all already made. Of course, he will only make each kind of hamburger once within a single day. Now he wants to know the maximal total value he can get after the whole day’s hard work, but he is too tired so this is your task now!
 

Input
The first line consists of an integer C(C<=50), indicating the number of test cases.
The first line of each case consists of two integers N,E(1<=N<=15,0<=E<=100) , indicating there are N kinds of hamburgers can be made and the initial energy he has.
The second line of each case contains N integers V1,V2…VN, (Vi<=1000)indicating the value of each kind of hamburger.
The third line of each case contains N integers E1,E2…EN, (Ei<=100)indicating the energy each kind of hamburger cost.
Then N lines follow, each line starts with an integer Qi, then Qi integers follow, indicating the hamburgers that making ith hamburger needs.
 

Output
For each line, output an integer indicating the maximum total value HamMagi can get.
 

Sample Input
1
4 90
243 464 307 298 
79 58 0 72
3 2 3 4
2 1 4
1 1
0
 

Sample Output
298
 

Source
HDU 2009-10 Programming Contest

//题意：
//一个人做汉堡包，每个汉堡包都有自己的花费和价值，

某些汉堡包必须要在其他的某一些汉堡包已经做好了的前题下才能制作，

给出这个人的初始钱数，问能实现的最大价值是多少。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 17;
int a[maxn][maxn];//需要满足的做汉堡包的先后顺序
int dp[1<<maxn];//dp[i]表示i状态时的最大价值，
int no_cost[1<<maxn];//money[i]表示的是i状态时的剩余的钱
int cost[maxn], get_v[maxn];
int n, money;
int judge(int m, int state)
{
    //检查是否满足做某汉堡包时题目给出的要在做他之前做的汉堡包都已经做了
    for(int i = 1; i <= a[m][0]; i++)
    {
        if(!(state & (1<<(a[m][i]-1))))
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&money);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&get_v[i]);
        }
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&cost[i]);
        }
        int tt;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&a[i][0]);
            for(int j = 1; j <= a[i][0]; j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        for(int i = 0; i <= (1<<n)-1; i++)
        {
            dp[i] = -1111;
            no_cost[i] = 0;
        }
        dp[0] = 0;
        no_cost[0] = money;
        int ansm = 0;
        for(int i = 0; i <= (1<<n)-1; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(i & 1<<(j-1))//如果第i个汉堡包已经做过就不再更新
                {
                    continue;
                }
                int now = i | (1<<(j-1));//做第i个汉堡包
                if(dp[now] < dp[i]+get_v[j] && judge(j,i) && no_cost[i] >= cost[j])
                {
                    dp[now] = dp[i]+get_v[j];
                    no_cost[now] = no_cost[i] - cost[j];
                    ansm = max(ansm, dp[now]);
                }
            }
        }
        printf("%d\n",ansm);
    }
    return 0;
}


HDU 3182 Hamburger Magi（状压dp）


联系
我们