这一题是01背包的题，不能用贪心~~不然会~~$\color{red}WA$
by wuenzi @ 2024-07-11 12:45:35
```cpp
#include <bits/stdc++.h>
using namespace std;
int dp[2500];
int main() {
int m, n;
cin >> m >> n;
int w[105], c[135];
for (int i = 0; i < n; i++) {
cin >> w[i] >> c[i];
}
for (int i = 0; i < n; i++) {
for (int j = m; j >= w[i]; j--) {
dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
}
}
cout << dp[m];
return 0;
}
```
by wuenzi @ 2024-07-11 12:46:39
@[DreamFlyboat](/user/924336) 这个题正解是 $dp$ 用贪心会出 $bug$。
状态转移方程：
```cpp
dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+s[i]);
```
最后求 ```tms[m][t]``` 的值即可。
by duminghao123 @ 2024-07-11 13:56:48
```python
#include <bits/stdc++.h>
using namespace std;
int w[105], val[105];
int dp[1005];
int t,m,res=-1;
int main()
{
cin>>t>>m;
for(int i=1;i<=m;i++)
{
cin>>w[i]>>val[i];
}
for(int i=1;i<=m;i++)
{
for(int j=t;j>=0;j--)
{
if(j>=w[i])
{
dp[j]=max(dp[j-w[i]]+val[i], dp[j]);
}
}
}
cout<<dp[t];
return 0;
}
```
这样子就可以
by York1121 @ 2024-07-14 11:13:37
也可以逆推，用一维数组，空间复杂度只有O(n)
```cpp
#include<bits/stdc++.h>
using namespace std;
int t,n,w[1020],v[1020],f[1020];
int main(){
cin>>t>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=n;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 230327liuyanzhe @ 2024-07-20 10:32:47