01背包变形

2018-06-17 20:42:24来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

普遍认为华中校园里有无数树木。

现在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

输入

1
3 10
5 10
5 10
4 12

输出

22


题目大意
题目意思就是一个01背包问题,但是它的数据是10的八次方,所以不能直接套用模板,这题需要做相应的变换
本来01背包需要创建一个二维数组 ,然后把重量进行dp,算出在当前重量所能达到的最大价值,但是会爆内存,
所以换了个思想,我dp每个价值能获得的最小重量,然后判断是否是小于输入给的那个限定重量即可;
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
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思想
 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:快速数论变换(NTT)小结

下一篇:【模板】三分法