LightOJ 1079 Just another Robbery （01背包）

题目链接

题意：Harry Potter要去抢银行（wtf？？？），有n个银行，对于每个银行，抢的话，能抢到Mi单位的钱，并有pi的概率被抓到。在各个银行被抓到是独立事件。总的被抓到的概率不能超过P。

解题关键：如果考虑各种情况存在某一次被抓住的概率，相当于是取 并集，这个比较麻烦。然而，n个独立事件都不被抓住的概率，相当于是取 交集，直接把要考虑到的事件的不被抓住的概率乘到一起就好了。这样就能把这道题转化为01背包的问题了。

不被抓概率！~物品体积　　（不被抓概率不低于某阈值，物品总体积不高于某阈值）

所抢金额~物品价值　　　　（显然）

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const double eps=1e-;

int n;

double P,Q;        //Q表示，可行域中，最小的不被抓住的概率

int m[];

double p[];

double q[];

double dp[];

int main()

{

    int T,kase=;

    scanf("%d",&T);

    while(T--)

    {

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

        Q=-P;

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

        {

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

            q[i]=-p[i];

        }

        memset(dp,,sizeof(dp));

        dp[]=;

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

        {

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

            {

                if(dp[j-m[i]]*q[i]<Q-eps) continue;

                dp[j]=max(dp[j],dp[j-m[i]]*q[i]);

            }

        }

        for(int i=;i>=;i--)

            if(dp[i]>eps)

            {

                printf("Case %d: %d\n",++kase,i);

                break;

            }

    }

}