http://acm.hdu.edu.cn/showproblem.php?pid=2955

题目大意：给你一个劫匪抢银行的最高安全概率，给你银行得到钱数，和劫匪在这个银行可以逃跑的概率，问你最多能抢多少钱

————————

按照一般的思路，背包的容量都想定义为最高安全概率，但是这是浮点数，所以只能用银行所有的钱数作为容量，dp中存储抢完这些钱被抓的概率是多少，然后变量dp的值，看看（1 - dp）什么时候比最高安全概率小，那时候抢到的钱就是安全的

#include <iostream>

#include <cstdio>

#include <string.h>

#include <cmath>

#include <algorithm>

#define eps 1e-9

using namespace std;

const int maxn = 1e5;

double dp[maxn];

double p[maxn];

int value[maxn];

int main()

{

    int t;

    scanf("%d",&t);

    double V; // 被抓可能性安全值

    int n;

    while(t--)

    {

        scanf("%lf %d",&V,&n);

        int value_sum = 0;

        for(int i = 0;i < n;i++)

        {

            scanf("%d %lf",&value[i],&p[i]);

            value_sum += value[i];

        }

        if ((V - 0) < eps)

        {

            cout<<0<<endl;

            continue;

        }

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

        dp[0] = 1;

        for(int i = 0;i < n;i++)

            for(int j = value_sum;j >= value[i];j--)

            {

                dp[j] = max(dp[j],dp[j - value[i]] * ( 1 - p[i]));

            }

        for(int j = value_sum;j >= 0;j--)

        {

            if(V - (1 - dp[j]) > eps)

            {

                cout<<j<<endl;

                break;

            }

        }

    }

    return 0;

}