DP：01背包

int w[1010];  // 每种物品的重量
int v[1010];  // 每种物品的价值
int dp[1010][1010];   // dp[i][j] 表示从前 i 种物品中选取体积之和不超过 j 的物品集合（的最大价值）

int main()
{
    int n, t; 
    cin >> n >> t;          // n 件物品，背包最大承重 t
    for(int i = 1; i <= n; ++i) 
        cin >> w[i] >> v[i];   // 输入第 i 件物品的重量 和 价值  
    for(int i = 1; i <= n; ++i)       // 枚举物品
        for(int j = 0; j <= t; ++j)   // 枚举重量：从 0 开始，然后 ++，最大不超过 t 
        {
            dp[i][j] = dp[i - 1][j];          // 不选择第 i 种物品（总存在，不需条件）              
            if(j >= w[i])                     // 选择第 i 种物品，需要能容下 w[i] 的条件
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);   // 保存最大价值
        }
    cout << dp[n][t] << endl;   // 输出结果：从前 n 种物品中选则体积不超过 t 的物品的最大价值
    return 0;
}