还是选与不选的问题,但是每个背包可以无限次选,所以这是个完全背包!
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
int f[N],w[N],t[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>w[i]>>t[i];
}
for(int i=1;i<=m;i++){
for(int j=t[i];j<=n;j++){
f[j]=max(f[j],f[j-t[i]]+w[i]);
}
}
cout<<f[n];
return 0;
}