Hamburger Magi

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

298

输入n e

n代表n个汉堡，  e代表最大负重，每个汉堡只能拿一次

接下来一行四个数表示 n个汉堡的价值

再一行表示n个汉堡的花费

再接下来n行表示 第i汉堡如果要的话 需要先拿哪几个

如案例  3 2 3 4 ，表示要拿  第一个汉堡要先拿 编号2 3 4 这三个汉堡

思路

历遍所有状态，求最大值

#include<stdio.h>
int nd[20],vi[20],ci[20];
int main()
{
    int t,n,c,i,j;
    int tn,tem,tt;
    int lim,ans,flag,allc,allv;
    int zuiduo,dangqian,youbian;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&c);
        for(i=0;i<n;i++)
            scanf("%d",&vi[i]);
        for(i=0;i<n;i++)
            scanf("%d",&ci[i]);

        for(i=0;i<n;i++)
        {
            tem=0;
            scanf("%d",&tn);
            while(tn--)
            {
                scanf("%d",&tt);
                tem|=(1<<(tt-1));
            }
            nd[i]=tem;
        }

        lim=1<<n;
        ans=0;
        for(i=0;i<lim;i++)//zhuangtai
        {
            allv=0;
            allc=0;
            zuiduo=15;
            dangqian=0;
            while(zuiduo--)
            {
                youbian=0;
                for(j=0;j<n;j++)//meigewei
                {
                    if((i>>j)&1&&((dangqian>>j)&1)==0)//xuyao
                    {
                        if((dangqian&nd[j])==nd[j])//条件符合
                        {
                            allv+=vi[j];
                            allc+=ci[j];
                            youbian=1;
                            dangqian|=1<<j;
                        }     
                    }
                }
                if(youbian==0)
                    break;
            }
            if(allc>c||allv<ans||dangqian!=i)
                continue;
            ans=allv; 
        }
        printf("%d\n",ans);

    }
    return 0;
}

hdu 3182 Hamburger Magi 状压

原文：http://blog.csdn.net/u013532224/article/details/40918055