Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
144867 | 黄恩宁 | 0/1背包问题 | C++ | 通过 | 100 | 4 MS | 4216 KB | 459 | 2024-04-27 15:50:43 |
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int NR=(1e3)+10,MR=(1e3)+10; int f[NR][MR],v[NR],w[NR]; int main() { int n,m,i,j; scanf("%d%d",&m,&n); for(i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]); //for(j=0;j<=m;j++) f[0][j]=0; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(j-w[i]>=0) f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]); else f[i][j]=f[i-1][j]; } printf("%d",f[n][m]); return 0; }