15755187277 2016-05-05 07:28:56
点我顶贴
收藏
删除
#include<iostream>
using namespace std;
#define X 101
#define max(a,b) (a>b)?a:b
int c[X],w[X],dp[X][101*X];
int main()
{
int T,M;
cin>>T>>M;
int i,j;
for(i=1;i<=M;i++)
cin>>c[i]>>w[i];
for(j=0;j<=T;j++) //首先计算dp[1][j]
{
if(j>=w[1]) dp[1][j]=w[1];
else dp[1][j]=0;
}
for(i=2;i<=M;i++)
for(j=0;j<=T;j++)
if(j>=c[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
else
dp[i][j]=dp[i-1][j];
cout<<dp[M][T];
return 0;
}