正解是要用背包的 (动态规划)@[EricOO7](/user/1070274) (不过写成这样也挺厉害了qwq)
ac代码:
```
#include <iostream>
using namespace std;
int d[1010],m,maxw;
int main()
{
scanf("%d %d",&maxw,&m);
int ti,vi;
for(int i=1;i<=m;i++)
{
scanf("%d %d",&ti,&vi);
for(int j=maxw;j>=ti;j--)
d[j]=max(d[j],vi+d[j-ti]);
}
printf("%d",d[maxw]);
return 0;
}
```
01背包,可以自己去看一下
by _____QWQ_____ @ 2024-02-21 12:44:47
@[EricOO7](/user/1070274) 你这得01背包啊
当然dp也可以
下面是我的代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int t,m,w[10005],val[10005];
int dp[1005][1005];
int main(){
scanf("%d%d",&t,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&w[i],&val[i]);
}
for(int i=1;i<=m;i++){
for(int j=t;j>=0;j--){
if(j>=w[i]){
dp[i][j]=max(dp[i-1][j-w[i]]+val[i],dp[i-1][j]);
}
else{
dp[i][j]=dp[i-1][j];
}
}
}
printf("%d",dp[m][t]);
return 0;
}
```
by liverxiwo @ 2024-02-21 12:48:09