题解：P1060 [NOIP2006 普及组] 开心的金明

本题算法：搜索，动态规划。

这里我给大家介绍一种用深度优先搜索的方法。要注意到本题金明要买的东西有以下几个特点：假设要选第

x

个物品，这个物品要么选，要么不选。所以我们可以从第一个物品开始搜索，如果前还够，就买，否则不买。注意，如果第

x

个物品选了，钱数要减少

money_i

。

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int v[maxn],p[maxn],maxi,m,money,c=0,ans[maxn];
void dfs(int x)
{
	if(x>m)
	{
		maxi=max(maxi,c);
		return ;
	}
	if(money-v[x]>=0)//选这个物品
	{
		ans[x]=1;
		money-=v[x];
		c+=p[x]*v[x];
		dfs(x+1);
		
		ans[x]=0;//否则dfs函数会退回来到当前这种情况
		money+=v[x];//把钱数补上
		c-=p[x]*v[x];//价值减少
		dfs(x+1);//再搜索下一个物品，与上一次搜索下一个物品不同的是：这个物品不会再选了。
	}
    else//否则不选
    {
    	ans[x]=0;
    	dfs(x+1);
	}
}
int main()
{
	maxi=INT_MIN;
	cin>>money>>m;
	for(int i=1;i<=m;i++) 
	{
		cin>>v[i]>>p[i];
	}
	dfs(1);
	cout<<maxi;
	return 0;
}

题解：P1060 [NOIP2006 普及组] 开心的金明

文章操作

相关推荐

评论

题解：P1060 [NOIP2006 普及组] 开心的金明