搜索题

萌宠菠菠乐园
2024-11-23 01:40

题目描述：鱼的种类有多种，但有些鱼会互相攻击对方，在给定一定数目的钱时，怎么买尽可能多的鱼，并且要求找出在买的鱼数目相同的情况下所花的钱是最多的一个方案。

测试用例

输入

1000 10
10 78
9 179
8 9
7 344
6 76
5 224
4 127
3 91
2 276
1 47
10 9
10 6
9 7
9 1
8 2
7 6
7 4
7 2
6 3
5 3
5 2
3 1
0 0

输出

5 702
1
5
7
8
10

#include < iostream >
using namespace std; const int MAXSIZE = 31 ; // 鱼的最大种类数
int m,n; // 输入的钱数和鱼种类数
bool attack[MAXSIZE][MAXSIZE]; // 鱼之间的攻击性
int fish[MAXSIZE]; // 鱼的价格
int p[MAXSIZE]; // 买鱼的策略
int pbest[MAXSIZE]; // 买鱼的最佳策略
int cone,best; // 买鱼的数目，最优数目
int sum,sumbest; // 买鱼的花费，最优花费

void Solve( int t)
{
bool bb;
int i;
p[t] = - 1 ;
do
{
p[t] = p[t] + 1 ;
if (p[t] == 1 )
{ // 买下这种鱼
++ cone;
sum += fish[t];
}
// 钱还有剩余
if (sum <= m)
{
bb = true ;
}
else
bb = false ;
if (bb == true && p[t] == 1 )
{
for (i = n;i > t; -- i)
{
// 判断当前鱼与前面选择的是否互相攻击
if (p[i] == 1 && attack[i][t] == true )
{
bb = false ;
break ;
}
}
}
if (bb == true )
{
if (t == 1 )
{ // 到最后一种鱼了
if (cone > best || (cone == best && sum > sumbest))
{ // 找到一个更优解
best = cone;
sumbest = sum;
for (i = 1 ;i < MAXSIZE; ++ i)
{
pbest[i] = p[i];
}
}
}
else
{ // 继续向下搜索
Solve(t - 1 );
}
} if (p[t] == 1 )
{ // 恢复到不买这种鱼的状态
-- cone;
sum -= fish[t];
}
} while (p[t] != 1 );
} void Output()
{ // 输出最优解
cout << best << " " << sumbest << endl;
for ( int i = 1 ;i <= n; ++ i)
{
if (pbest[i] == 1 )
{
cout <> m >> n;
// 各种鱼的价格
for (i = 0 ;i < n; ++ i)
{
cin >> nId >> nPrice;
fish[nId] = nPrice;
}
// 鱼之间互相攻击对方的关系
while (cin >> s >> t && (s != 0 && t != 0 ))
{
attack[s][t] = true ;
attack[t][s] = true ;
}
best = 0 ; // 鱼的最优数目
sumbest = 0 ; // 鱼的最优花费
Solve(n);
Output();
system( " pause " );
return 0 ;
}