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

别人内卷我在躺平 · 2025-01-16 09:48:43 · 题解

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

这里我给大家介绍一种用深度优先搜索的方法。要注意到本题金明要买的东西有以下几个特点：假设要选第 x 个物品，这个物品要么选，要么不选。所以我们可以从第一个物品开始搜索，如果前还够，就买，否则不买。注意，如果第 x 个物品选了，钱数要减少 money_i。

#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;
}