- 灰灰的婚姻 / 【模板】01背包DP
- 2024-08-24 18:58:00 @
#include <bits/stdc++.h>
using namespace std;
int w[1009],c[1009],f[1009][100009];
int n,m;
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>c[i];
cin>>w[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j<=w[i]) f[i][j]=f[i-1][j];
else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);
}
}
cout<<f[n][m];
return 0;
}
某些瑕疵:
感觉这道题没有数据范围???
1 条评论
-
XzyStudio (admin) LV 8 MOD RP++ 机房蒟蒻 tayz @ 2024-08-26 16:37:55
后面可能需要遍历一遍
f[n][i]
来找出最大答案?
- 1