luogu1048 【2005普及】采药（背包dp）

01背包。

#include<cstdio> #include<cstring> int m,t,f[1001],p[101],w[101]; int main(){ //freopen("a.in","r",stdin); scanf("%d%d",&t,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&w[i],&p[i]); } memset(f,0,sizeof(f)); for(int i=1;i<=m;i++) for(int j=t;j>=w[i];j--) if(f[j-w[i]]+p[i]>f[j]) f[j]=f[j-w[i]]+p[i]; printf("%d",f[t]); return 0; }