01背包

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N=1010;
int v[N],w[N],dp[N][N];
int n, m;

int main()
{
  scanf("%d%d",&n,&m);//n是物品数量，m是背包容量

  for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);

  for(int i=1;i<=n;i++) {
    for(int j=1;j<=m;j++)
    {
        if(v[i] > j)
        {
            dp[i][j] = dp[i - 1][j];
        } else
        {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
  }
  printf("%d",dp[n][m]);
  return 0;
}