首页 > > 程序设计 > C/C++ >

01背包变形

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

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

现在HUST得到了一块容量为C的大土地种植树木。我们有n棵树可以种植在里面。每棵树使HUST变得美丽，这是由树的价值决定的。另外每个树有一个区域的成本，这意味着我们需要的费用C _我的土地，厂房面积。
我们知道所有树木的成本和价值。现在，HUSTers想要最大化土地上种植的树木的价值。你能帮助他们吗？

输入描述：

有多种情况。
第一行是一个整数T（T≤10），它是测试用例的数量。
对于每一个测试情况下，第一线路是两个数n（1≤n≤100）和C（1≤C≤10 ），种子的数量和土地的容量。然后接下来的n行，每行包含两个整数?

_我

（1≤C

_我

≤10

⁶

）和v

_我

（1≤v

_我

≤100），空间和成本的第i个树的值。

输出描述：

对于每种情况，输出一个整数，这意味着可以在土地上种植的树木的最大值。

示例1

输入

输出

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
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有