01背包

经典01背包
.cpp
#include<iostream>
using namespace std;
int t,n,a[110],b[110],dp[110][100010];
int main()
{
scanf("%d%d",&t,&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=t;j++)
{
if(j>=a[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+b[i]);
else
dp[i][j]=dp[i-1][j];
}
printf("%d",dp[n][t]);
return 0;
}