Robberies HDU 2955(01背包)

http://acm.hust.edu.cn/vjudge/contest/125771#problem/G

密码：zznuacm

题意：现给出逃跑的警戒值（也就是超过这个值就会被抓），问你在不超过这个值的前提下，最大能偷走的钱的数目。

分析：由于警戒值是浮点数，不能当做背包容量。那么我们需要换一件东西当背包容量，那么只有是钱的总数了，然后将警戒值当做价值，再按照01背包的模板来一遍就好了。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <math.h>

using namespace std;

#define INF 0x3f3f3f3f
const int maxn = 110;

typedef long long LL;
float p[maxn], dp[11000];
int m[maxn];

///可以思考下为什么只能用逃跑成功的概率来写
int main()
{
    int T, n, sum;
    float P;

    scanf("%d", &T);

    while(T --)
    {
        scanf("%f %d", &P, &n);
        P =1-P;///逃跑成功概率
        sum = 0;

        for(int i=1; i<=n; i++)
        {
            scanf("%d %f", &m[i], &p[i]);
            sum += m[i];
            p[i] = 1-p[i];
        }

        memset(dp, 0, sizeof(dp));

        dp[0] = 1;///若一件物品都不偷，那么安全度肯定为1了

        for(int i=1; i<=n; i++)
        {
            for(int j=sum; j>=m[i]; j--)
            {
                dp[j] = max(dp[j], dp[j-m[i]]*p[i]);
            }
        }

        int i;

        for(i=sum; i>=0; i--)
        {
            if(dp[i]>=P)///寻找当安全度高于或等于逃跑成功的概率，这时得到的偷得钱数肯定是最大值
                break;
        }

        printf("%d
", i);
    }
    return 0;
}

View Code

Robberies HDU 2955(01背包)

相关推荐