王伯买鱼【深搜+剪枝】

答案:2 悬赏:0 手机版

解决时间 2021-02-11 16:08

提问者网友：愿为果
2021-02-11 11:30

王伯买鱼【深搜+剪枝】
Time Limit:1000MS Memory Limit:65536K
Total Submit:52 Accepted:21
Description
王伯买鱼（fish.pas\c\cpp）
王伯退休后开始养鱼。他一早起来就赶去动物公园，发现这个世界的鱼真不少，五光十色、色彩斑调，大的、小的，什么都有。这些鱼实在是太美了，买的人越来越多，湖里的鱼越来越少。没有美丽的鱼。哪里有美丽的湖？于是动物公园不得不规定，对于每种鱼，每个人最多只能买一条。并且有些鱼是不能一起买的，因为它们之间会互相争斗吞食。
王伯想买尽可能多的鱼，但很可惜，他的资金有限。他冥思苦想，不知如何是好。请编写一个程序帮助他。如果有多个方案都能买尽可能多的鱼，选择所花资金最多的一个。
Input
输入文件fish.in的第一行为两个正整数M（M<=100），N（N＜=30），分别表示王伯的资金和鱼的种类。以下 N 行，每行有两个正整数S（ l=＜S＜=N），T，分别表示某种鱼的编号以及该鱼的价格。
接着，每行有两个整数P，Q。当P，Q均大于0时，表示P，Q不能共处；当P，Q均等于0时，表示输入文件的结束。
Output
输出文件 fish.out 的第一行为两个正整数X，Y，分别表示所买鱼的条数和总花费。以下X行，每行有一个正整数，表示所买鱼的编号。编号按升序排列输出。
如果题目有多个解，只需输出其中的一个。
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
2
4
5
6

放了很久了，有谁会啊！！！！！！！！！！！

最佳答案

五星知识达人网友：封刀令
2021-02-11 11:55

晕，这事什么问题哦

全部回答

1楼网友：举杯邀酒敬孤独
2021-02-11 12:43

#include <iostream> #include <iomanip> using namespace std;

//定义一个结构，用来存放鱼的基本信息 typedef struct _fish{ int id; //鱼的编号 int price; //鱼的价钱 }fish;

//定义个类，用于存放买家信息和方法 class findsolution { private: int money; //资金 int total; //鱼的种类 fish* data; //用于存放鱼的数据 int** relation; //一个2维用于存放鱼的共存关系

public: findsolution(int _money, int _total) : money(_money), total(_total) { data = new fish[total]; //分配鱼的数据的空间 //分配一个二维数组的空间，来存放鱼的共存关系 relation = new int*[total]; int i,j; for (i=0; i<total; i++){ relation[i] = new int[total]; } //初始化 for (i=0; i<total; i++){ for (j=0; j<total; j++){ relation[i][j] = 0; } }

}

~findsolution(){ delete [] data; for (int i=0; i<total; i++){ delete [] relation[i]; } delete [] relation; }

//输入鱼的信息 void inputfishdata(){ cout<<"输入鱼的编号和价格\n输入格式为: 鱼的编号鱼的价格"<<endl; for (int i=0; i<total; i++){ cin>>data[i].id>>data[i].price; } }

//输入鱼的关系表 void inputfishrelationship(){ cout<<"输入鱼与鱼的关系表\n输入格式为: 鱼的编号鱼的编号，以0 0结束"<<endl; int left, right; cin>>left>>right; while (left!=0 && right !=0){ //检查输入是否正确 if (check(left)&&check(right)){ relation[getindex(left)][getindex(right)] = 1; relation[getindex(right)][getindex(left)] = 1; } cin>>left>>right; } }

bool check(int _id){ if (_id ==0){ cout<<"鱼的编号不能为0！"<<endl; return false; } for (int i=0; i<total; i++) if (_id == data[i].id) return true; //如果输入的数和已有的鱼的编号相符 cout<<_id<<"并不是已有的鱼的编号"<<endl; return false; }

//通过输入的编号，返回该鱼在数据库里的编号 int getindex(int _id){ for (int i=0; i<total; i++){ if (data[i].id == _id) return i; } return 0; }

//输出详细的鱼的信息 void printinfo(){ cout<<endl<<setw(8)<<"编号"<<setw(8)<<"价格"<<endl; int i,j; for (i=0; i<total; i++){ cout<<setw(8)<<data[i].id<<setw(8)<<data[i].price<<endl; } cout<<"\n\n鱼种类件关系表。数字为鱼的编号，x代表不能共存"<<endl; cout<<setw(10)<<" "; for (i=0; i<total; i++) cout<<setw(3)<<data[i].id; for (i=0; i<total; i++){ cout<<endl<<setw(10)<<data[i].id; for (j=0; j<total; j++){ if (relation[i][j] == 0) cout<<setw(3)<<" "; if (relation[i][j] == 1) cout<<setw(3)<<"x"; } } cout<<"\n\n"; }

//计算出最合适的方式 void getsolution(){ int totalprice, i, j, count=0, maxcount=0; int* list = new int[total]; cout<<"\n输出所有的方法:"<<endl; for(i=0;i<total;i++){ totalprice = data[i].price; count=1; cout<<endl<<data[i].id<<" "; for(j=0;j<total;j++){ if (relation[i][j]==0&&i!=j){ totalprice+=data[j].price; if (totalprice<=money){ count++; if (maxcount<count) maxcount=count; cout<<data[j].id<<" "; } } } } //知道maxcount后，就可以选择最好的方法了 int index; cout<<endl<<"\n最佳的方法为:\n"; for(i=0;i<total;i++){ totalprice = data[i].price; index=0; list[index]=data[i].id; for(j=0;j<total;j++){ if (relation[i][j]==0&&i!=j){ totalprice+=data[j].price; if (totalprice<=money){ index++; list[index]=data[j].id; } } } if (index == maxcount-1){ for(int n=0; n<=index; n++){ cout<<list[n]<<" "; } delete [] list; return; } } } };

//测试 int main(){ cout<<"输入老头儿的钱和鱼的种类(格式为: 钱种类): "<<endl; int money, total; cin>>money>>total; findsolution test(money, total); test.inputfishdata(); test.inputfishrelationship(); test.printinfo(); test.getsolution(); cout<<endl; return 0; }

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息