```cpp
#include <bits/stdc++.h>
#define nx 1009
using namespace std;
int t,m;
int t1[nx];
int w1[nx];
//dp[i][j]表示前i件物品放入容量为j的背包所需要
int dp[nx][nx];
int main(){
cin>>t>>m;
for(int i = 1;i<=m;++i){
cin>>t1[i];
cin>>w1[i];
}
//即把前0件物品放入任意背包所得价值皆为0
for(int i = 1;i<=m;++i){
for (int j = 1;j < t1[i];j ++)
dp[i][j] = dp[i - 1][j];
for(int j = t1[i];j<=t;++j){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-t1[i]]+w1[i]);
}
}
cout<<dp[m][t];
return 0;
}
```
@[Rhss](/user/684890)
这样的,状态的答案是m, t,而不是过程,这是DP的一个重点,还有,你不能选的地方应该要先获取上面的信息,一直传下去的
by char_cha_ch @ 2022-08-03 03:58:40
数组开大于1000
by TL张汐卉0708 @ 2022-08-03 08:59:51
for(int i=1;i<=m;i++)
{
for(int j=0;j<=t;j++)
{
if(j>=w[i])
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);
else
f[i][j]=f[i-1][j];
}
}
cout<<f[m][t];
return 0;
}//核心DP☻
by TL张汐卉0708 @ 2022-08-03 09:02:49
@[kirihara233](/user/701221) 感谢大佬
by Rhss @ 2022-08-03 18:10:04