普遍认为华中校园里有无数树木。
现在HUST得到了一块容量为C的大土地种植树木。我们有n棵树可以种植在里面。每棵树使HUST变得美丽，这是由树的价值决定的。另外每个树有一个区域的成本，这意味着我们需要的费用C 我 的土地，厂房面积。 我们知道所有树木的成本和价值。现在，HUSTers想要最大化土地上种植的树木的价值。你能帮助他们吗？
输入描述：
有多种情况。 第一行是一个整数T（T≤10），它是测试用例的数量。 对于每一个测试情况下，第一线路是两个数n（1≤n≤100）和C（1≤C≤10 ），种子的数量和土地的容量。然后接下来的n行，每行包含两个整数Ç
我
（1≤C
我
≤10
6
）和v
我
（1≤v
我
≤100），空间和成本的第i个树的值。
输出描述：
对于每种情况，输出一个整数，这意味着可以在土地上种植的树木的最大值。
示例1
输入
13 105 105 104 12
输出
22 题目大意 题目意思就是一个01背包问题，但是它的数据是10的八次方，所以不能直接套用模板，这题需要做相应的变换 本来01背包需要创建一个二维数组 ，然后把重量进行dp，算出在当前重量所能达到的最大价值，但是会爆内存， 所以换了个思想，我dp每个价值能获得的最小重量，然后判断是否是小于输入给的那个限定重量即可；
#include#include #include #include const int MAX = 1e2 + 5;const int MAXSIZE = 0x3f3f3f3f;using namespace std; int t, n, C, v[MAX], c[MAX];int main(){ int dp[10005]; int maxV; scanf("%d", &t); while (t--) { memset(dp, MAXSIZE, sizeof(dp)); maxV = 0; scanf("%d %d", &n, &C); for (int i = 0; i < n; i++) { scanf("%d %d", &c[i], &v[i]); maxV += v[i]; } dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = maxV; j >= v[i]; j--) { dp[j] = min(dp[j], dp[j - v[i]] + c[i]); } } for (int i = maxV; i >= 0; i--){ if (dp[i] <= C){ printf("%d\n", i); break; } } } return 0;}
还有一个运用到滚动数组（可以很大的节省内存），下次贴 借用两个大牛博客 https://www.cnblogs.com/GNLin0820/p/6434693.html https://blog.csdn.net/u012965373/article/details/52180788 通过这题熟练了01背包，加深了dp思想