【正经题解】采药

深度优先搜索

#include<iostream>
#include<cmath>//头文件
using namespace std;
int f[105][1005];//数组一定要多开几个，不然WA
int m,n,mi[105],vi[105];
int dfs(int x,int sumW)//把一个参数作为该函数的函数类型（优化一）
    {
    if(sumW>m)return -10000;//时间不能超出欧！
    if(f[x][sumW]) return f[x][sumW];//用一个数组来储存每一次dfs的数值，避免重复（优化二）
    if(x==n+1) return 0;//到末尾了就返回0
    f[x][sumW]=max(dfs(x****umW+mi[x])+vi[x],dfs(x****umW));//取最大值，没啥好说的
    return f[x][sumW];//输出最大值
}
int main(){
    cin>>m>>n;
    for(int i=0;i<n;i++){
        cin>>mi[i]>>vi[i];
    }
    cout<<dfs(0,0)<<endl;
    return 0;
}