@[CNMIOS](/user/1070915) 此题没必要用回溯，用01背包即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
int M,T,w[100001],v[100001],f[100001];
int main(){
cin>>T>>M;
for(int i=1;i<=M;i++) scanf("%d%d",&w[i],&v[i]);
for(int i=1;i<=M;i++){
for(int j=T;j>=w[i];j--){
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
}
cout<<f[T];
return 0;
}
```
by tuxxx @ 2024-05-29 22:51:52
@[CNMIOS](/user/1070915) 应该加个变量记录最大价值吧
```cpp
#include<iostream>
using namespace std;
int t,m,ans,maxans=0;
int a[105],b[105];
void dfs(int x,int y){
if(y>m){
maxans=max(maxans,ans);
return;
}
if(x-a[y]>=0){
ans+=b[y];
dfs(x-a[y],y+1);
ans-=b[y];
}
dfs(x,y+1);
}
int main(){
cin >> t >> m;
for(int i=1;i<=m;i++){
cin >> a[i] >> b[i];
}
dfs(t,1);
cout << maxans;
return 0;
}
```
by sansesantongshun @ 2024-07-06 21:22:50
@[tuxxx](/user/371749) 别人要写 dfs 你说 01 背包，能不能不要发这种回复
by sansesantongshun @ 2024-07-06 21:24:43
@[sansesantongshun](/user/866613) thx 贴结
by CNMIOS @ 2024-07-08 09:46:02