王伯买鱼问题

djkpengjun

                问题描述
   王伯退休后开始养鱼。他一早起来就赶去动物公园，发现这个世界的鱼真不少，五光十色、色彩斑斓，大的、小的，什么样的都有。这些鱼实在太美了，买的人越来越多，湖里的鱼越来越少。没有美丽的鱼，哪里有美丽的湖？于是动物公园不得不规定，对于每种鱼，每个人最多只能买一条。并且有些鱼是不能一起买的，因为放在一起他们相互争斗吞食。
   王伯想买尽可能多的鱼，但很可惜，他的资金有限。他冥思苦想，不知如何是好。请编程帮他，如果有多个方案能买尽可能多的鱼，选择所花资金最多的一种方案。
   输入：第一行：资金m（#include #include #include #include using namespace std;vector > all;const int maxn=30;//int price[maxn+1]={0,70,50,30,40,40,30,50}; //各种鱼的价格int  price[maxn+1];int killed[maxn+1];int  enemy[maxn+1];//初始化敌者数组void  init(int** a,int m){        for(int i=1;i    {        for(int j=1;j            if(a[j]==1)            {                enemy++;//按行计数            }        killed=0;    }}bool  check(int enemy[],int n){    //全部要么被杀掉，要么已经无敌人了，才算成功    for(int i=1;i        if(enemy!=0 && !killed)            return false;    return true;}void search(int** a,int m,int tag){    //先检查再说    if(check(enemy,m)==true)    {        vector tmp;        int cost=0;  //总价钱        for(int i=1;i            if(enemy==0)  //无敌者            {                tmp.push_back(i);                cost+=price;            }        tmp.push_back(cost);//最后一个元素是总价钱        all.push_back(tmp);    }else{  //下面一定有没有被杀且不为0的元素        //只在非0且没有被杀掉的元素中找最小值        int min=INT_MAX;        for(int i=1;i        if(enemy && !killed)        {            if(enemy            {                min  = enemy;            }        }        //深搜,剪枝        for(int i=1;i        if(enemy==min && !killed)        {            //杀掉敌人j,并更新敌人数组，同盟者可以少一个敌人了,注意这个敌人可能早就被杀掉了            for(int j=1;j                if(a[j]==1&& !killed[j])                {                    killed[j]=tag;     //j这个敌人被杀掉了                    //k为i同盟者,包括i                    for(int k=1;k                        if(a[j][k]==1)                           enemy[k]--;                }            search(a,m,tag-1);            //复活敌人            for(int j=1;j                if(a[j]==1&& killed[j]==tag)                {                    killed[j]=0;     //j这个敌人复活了                    //k为i同盟者,包括i                    for(int k=1;k                        if(a[j][k]==1)                           enemy[k]++;                }        }    }        }/*example//a为各鱼之间的共存性,竞争对手int a[maxn+1][maxn+1]={    0,0,0,0,0,0,0,0,    0,0,0,0,1,0,0,1,    0,0,0,0,0,0,0,0,    0,0,0,0,1,1,1,0,    0,1,0,1,0,0,0,0,    0,0,0,1,0,0,0,1,    0,0,0,1,0,0,0,0,    0,1,0,0,0,1,0,0,};*/main(){    int money,m;    cin>>money>>m;    int j,k;    for(int i=1;i    {        cin>>j>>k;        price[j]=k;        }    int* opponents[m+1];    for(int i=1;i            opponents=new int[m+1];        cin>>j>>k;    while(j!=0)    {        opponents[j][k]=1;        opponents[k][j]=1;        cin>>j>>k;                }    init(opponents,m);    search(opponents,m,m);    cout    j=0;    for(int i=1;i        if(all.back()> all[j].back() &&  all.back()            j=i;    cout    copy(all[j].begin(),all[j].end()-1,ostream_iterator(cout,"\n") );    for(int i=1;i        delete[]  opponents;}
               
               
               
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/104733/showart_2115622.html