背包DP代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e3+1;
int n,m,v[N],c[N];
//从第i个物品开始挑选总重量不大于sumv的部分  
int dfs(int now,int sumv){
int res;
if(now==n+1) return res=0;//已经没有剩余物品
if(sumv<v[now]) res=dfs(now+1,sumv);//无法挑选第i个物品
else res=max(dfs(now+1,sumv),dfs(now+1,sumv-v[now])+c[now]);//比较挑和不挑的情况，选取最大的情况
return res;
}
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&c[i]);
printf("%d",dfs(1,m));
return 0;
}