經(jīng)典的背包問題.
#include <iostream>
#include <algorithm>
using namespace std;
int w[3500];
int v[3500];
int dp[13000];
int main ()
{
int n,m;
int i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d%d",&w[i],&v[i]);
}
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
for(j=m;j>=w[i];j--)
{
if(dp[j]<dp[j-w[i]]+v[i])
dp[j]=dp[j-w[i]]+v[i];
}
}
printf("%d\n",dp[m]);
return 0;
}