HDU3182

HDU3182

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种汉堡，每种汉堡有自己的成本和价值（成本是消耗能量），而且有的汉堡必须在别的汉堡的基础上才能制作完成，现在我们有E的能量，问能做的汉堡的最大价值是多少？（每种汉堡只能做一个，作为别的汉堡的原料的汉堡在制作完成别的汉堡后并没有被消耗，任然存在）。

解析：
由于题目最多只有15种汉堡，所以我们可以用状态压缩来表示每种汉堡的状态，这道题如果没有某种汉堡能作为别的汉堡的原料这个要求，则是01背包，加上这个条件后就复杂了些许。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;int dp[(1<<15)+10];
int need[20];
int price[20];
int val[20];int main()
{int T,y,n;scanf("%d",&T);while(T--){int num,enery;scanf("%d%d",&num,&enery);for(int i=1;i<=num;i++){scanf("%d",&val[i]);}for(int i=1;i<=num;i++){scanf("%d",&price[i]);}for(int i=1;i<=num;i++){need[i]=0;scanf("%d",&n);for(int j=1;j<=n;j++){scanf("%d",&y);need[i]|=(1<<(y-1));}}memset(dp,-1,sizeof(dp));dp[0]=0;int Max=0;for(int i=0;i<(1<<num);i++){int cost=0,bit=0;while(i>>bit){if((i>>bit)&1)cost+=price[bit+1];bit++;}if(cost>enery||dp[i]==-1)continue;for(int j=1;j<=num;j++){if(!(i&(1<<(j-1)))){	if((cost+price[j])<=enery){if((need[j]&i)==need[j]){dp[i|(1<<(j-1))]=dp[i]+val[j];if(Max<dp[i|(1<<(j-1))])Max=dp[i|(1<<(j-1))];}}}}}printf("%dn",Max);}	return 0;
}