Skip to main content

启发式搜索

参考资料​

例题​

洛谷 P1048 [NOIP 2005 普及组] 采药​

洛谷 P1048 [NOIP 2005 普及组] 采药

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

Code (2)
#include <bits/stdc++.h>
using namespace std;

const int N=105;
struct Node
{
	int a,b;
	double f;
	bool operator<(const Node &rhs){return f>rhs.f;}
}a[N];
int n,m,ans=0;
int f(int t,int v)
{
	int res=0;
	for(int i=1;t+i<=n;i++)
	{
		if(v<a[t+i].a)return res+v*a[t+i].f;
		v-=a[t+i].a;
		res+=a[t+i].b;
	}
	return res;
}
void work(int t,int p,int v)
{
	ans=max(ans,v);
	if(t>n)return;
	if(f(t,p)+v>ans)work(t+1,p,v);
	if(a[t].a<=p)work(t+1,p-a[t].a,v+a[t].b);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].a>>a[i].b;
		a[i].f=a[i].b*1.0/a[i].a;
	}
	sort(a+1,a+n+1);
	work(1,m,0);
	cout<<ans<<'\n';
	return 0;
}