HDU3182-状压dp

川长思鸟来 2022-07-13 14:56 171阅读 0赞

# Hamburger Magi #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 737    Accepted Submission(s): 255**

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

**题目大意：现在你需要制作n个汉堡（编号为1-n）每个汉堡都有一个权值和一个需要消耗的能量，并且并且每个的汉堡的制作必须要制作完其他k（可以为0）个汉堡（编号）才能制作该汉堡，现在你有E能量，问你能够获得的最大权值是多少？**

**题目思路：刚开始看这个题的时候没有啥思路，就想着暴力去遍历所有的汉堡的子集，然后在判断是否成立，后来想想这样或许可以但是有可能会超时，并且也太麻烦了，然后看到其他大佬用的状压dp做的，就试着去想想，然后看到n只有15，只需用15个状态位来表示就可以，最大也就1<<15，觉得这样完全可做，所以我们就可以去枚举状态，当当前状态存在权值时然后就去枚举其他不在该状态里的汉堡然后在判断其他汉堡需要的状态在不在该状态里面（这个可以用按位与来判断），如果在就更新新的状态的权值，并且记录消耗的能量，最后只需找出所有状态的权值的最大值。**

**AC代码：**

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    
    using namespace std;
    
    class DP{
    public:
        int n,E,bit;
        int v[20],e[20];
        int dp[50000][2],need[20][20];
        void init(){
            bit = (1<<n)-1;
            for(int i=0;i<=bit;i++)dp[i][0]=-1,dp[i][1]=-1;
        }
        void sove(){
            int ans = 0;
            dp[0][0]=0;
            dp[0][1]=0;
            for(int i=0;i<=bit;i++){
                if(dp[i][0]==-1)continue;
                for(int j=n-1;j>=0;j--){
                    int flag=1;
                    if(i&(1<<j))continue;
                    for(int k=1;k<=need[j][0];k++){
                        if(!(i&(1<<(need[j][k]-1)))){
                            flag=0;
                            break;
                        }
                    }
                    if(flag){
                        if(dp[i][1]+e[j]<=E){
                            dp[i|(1<<j)][1]=dp[i][1]+e[j];
                            dp[i|(1<<j)][0]=dp[i][0]+v[j];
                            ans=max(ans,dp[i|(1<<j)][0]);
                        }
                    }
                }
            }
            printf("%d\n",ans);
        }
    
    }dp;
    
    int main()
    {
        int T;cin>>T;
        while(T--){
            scanf("%d%d",&dp.n,&dp.E);
            dp.init();
            for(int i=0;i<dp.n;i++)
                scanf("%d",&dp.v[i]);
            for(int i=0;i<dp.n;i++)
                scanf("%d",&dp.e[i]);
            for(int i=0;i<dp.n;i++){
                scanf("%d",&dp.need[i][0]);
                for(int j=1;j<=dp.need[i][0];j++){
                    scanf("%d",&dp.need[i][j]);
                }
            }
            dp.sove();
        }
    
        return 0;
    }