赤裸裸的0-1背包问题,入门题啊
View Code
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int dp[12883]; int w[3400],p[3400]; int main() { int n, m, i, j; while(~scanf("%d%d",&n,&m)) { for(i=1;i<=n;i++) scanf("%d%d",&w[i],&p[i]); memset(dp,0,sizeof(int)*(n+1)); for(i=1;i<=n;i++) { for(j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+p[i]); } printf("%d\n",dp[m]); } return 0; }