吴奶奶买鱼

Description

吴奶奶有个可爱的外孙女——琪琪，她很喜欢小动物，尤其喜欢养鱼。为了让小孙女养到漂亮的小鱼，吴奶奶一大早就到花鸟鱼虫市场买鱼。这个市场可真大，里面有各种各样的宠物，就连宠物鱼都有好几十种。这些鱼实在是太美了，买的人越来越多，可是因为货源有限，卖鱼的老板不得不规定：同一种鱼，每个人最多只能买一条，并且有些鱼是不能一起买的，因为它们之间会互相争斗吞食。 吴奶奶想尽可能地买多些鱼，但可惜，她的资金有限，这可怎么办好呢？请编写一个程序帮助她。如果有多个方案都能买到尽可能多的鱼，则选择所花资金最多的一个。

Input

输入文件的第一行为两个正整数M(M≤1000)，N(N≤30)，分别表示吴奶奶的资金和鱼的种类。以下N行，每行有两个正整数S（1≤S≤N），T，分别表示某种鱼的编号以及该鱼的价格。 接着，每行有两个整数P,Q。当P,Q大于0时，表示P,Q不能共处；当P,Q均等于0时，表示输入文件的结束。

Output

文件的第一行为两个正整数X,Y，分别表示所买鱼的条数和总花费。

Sample Input

170 7 1 70 2 50 3 30 4 40 5 40 6 30 7 20 1 4 1 7 3 4 3 5 5 7 6 7 0 0

Sample Output

4 160

其实就是0/1背包，加上一些限制条件，可以用搜索AC的

下面是AC代码：

#include<iostream>

using namespace std;

int need[100];

int f[100][100];

int ans,i,l=0,n,m,num;

int hash[100];

int ansh[100];

void dfs(int cur,int sum,int fish)

{

int thash[31];

if(cur>n)

{

if(num<fish||(num==fish&&sum>ans))

{

num=fish;

ans=sum;

}

return ;

}

if(fish+n-cur+1<num) return;

if(!hash[cur]&&sum+need[cur]<=m)

{

for(i=1;i<=n;i++)

thash[i]=hash[i];

hash[cur]=2;

for(i=1;i<=n;i++)

{

if(f[cur][i]&&!hash[i])

hash[i]=1;

}

dfs(cur+1,sum+need[cur],fish+1);

for(i=1;i<=n;i++)

hash[i]=thash[i];

hash[cur]=0;

}

dfs(cur+1,sum,fish);

}

int main()

{

int a,b,i,j;

scanf("%d%d",&m,&n);

l=0;ans=0,num=0;

for(i=1;i<=n;i++)

{

scanf("%d",&j);

scanf("%d",&need[j]);

}

scanf("%d%d",&a,&b);

while(a!=0||b!=0)

{

f[a][b]=1; f[b][a]=1;

scanf("%d%d",&a,&b);

}

dfs(1,0,0);

printf("%d %d",num,ans);

return 0;

}

cpp

cpp

相关知识

奥兰奶奶宠物值得买吗
奶奶把草鱼当宠物养了25年
北京猫奶奶，为了救助毛孩子，年纪八十却仍然日复一日的救助！
被奶奶带大的奶牛猫，奶奶生病后，猫咪搜集玩具一起守护奶奶
你到市场去买鱼，应该买（）
无锡买金毛犬宠物基地（无锡新吴区）买金毛犬去哪里买比较好
奶奶的QQ宠物作文
吴山吧
爱养小动物的奶奶作文
dnf奥兰奶奶任务多少级可以领取（奥兰奶奶宠物升级任务还有吗）

网址: 吴奶奶买鱼 https://www.mcbbbk.com/newsview1298861.html