链接：
https
：//www.nowcoder.com/acm/contest/119/F来源：牛客网
：//www.nowcoder.com/acm/contest/119/F来源：牛客网
普遍认为华中校园里有无数树木。
现在HUST得到了一块容量为C的大土地种植树木。我们有n棵树可以种植在里面。每棵树使HUST变得美丽，这是由树的价值决定的。另外每个树有一个区域的成本，这意味着我们需要的费用C 我 的土地，厂房面积。
我们知道所有树木的成本和价值。现在，HUSTers想要最大化土地上种植的树木的价值。你能帮助他们吗？
现在HUST得到了一块容量为C的大土地种植树木。我们有n棵树可以种植在里面。每棵树使HUST变得美丽，这是由树的价值决定的。另外每个树有一个区域的成本，这意味着我们需要的费用C 我 的土地，厂房面积。
我们知道所有树木的成本和价值。现在，HUSTers想要最大化土地上种植的树木的价值。你能帮助他们吗？
输入描述：
有多种情况。 第一行是一个整数T（T≤10），它是测试用例的数量。 对于每一个测试情况下，第一线路是两个数n（1≤n≤100）和C（1≤C≤10 8），种子的数量和土地的容量。 然后接下来的n行，每行包含两个整数? 我（1≤C 我 ≤10 6）和v 我（1≤v 我 ≤100），空间和成本的第i个树的值。
输出描述：
对于每种情况，输出一个整数，这意味着可以在土地上种植的树木的最大值。
示例1
输入
1 3 10 5 10 5 10 4 12
输出
22
#include<iostream>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 10005;
int dp[maxn];
int w[maxn];
int v[maxn];
int main()
{int T;cin >> T;while(T--){memset(dp, INF, sizeof(dp));int n,V,sum = 0;cin >> n >> V;for (int i = 0; i < n; i++){cin >> w[i] >> v[i];sum += v[i];}dp[0] = 0;for (int i = 0; i < n; i++){for (int j = sum; j >= v[i]; j--){dp[j] = min(dp[j], dp[j - v[i]] + w[i]);}}for (int i = sum; i >= 0; i--){if(dp[i] <= V){cout << i << endl;break;}}}
}