【LightOJ-1079 Just another Robbery 】概率01背包

LightOJ-1079 Just another Robbery

题意

有n个银行，第i个银行有$M_i$元，抢劫第i个银行被逮捕的概率为$p_i$，现在想知道被逮捕概率小于P的条件下，最多可以抢多少钱。

做法

首先这种dp，我们发现一个不能作为dp维度的实数要计算，就要把这个维度转换为dp值的定义，于是我们用dp[i][j]表示前i个银行抢劫j元不被逮捕的概率，dp的转移式很显然，就是类似01背包的转移式。
最后对于所有满足dp[i][j]>=1-P的dp值取最大的i即可。

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
const double eps = 1e-10;
const int maxn = 1e5+5;
int sgn(double x)
{
    if(fabs(x)<eps) return 0;if(x<0) return -1;return 1;
}
struct data
{
    int m;double p;
}x[maxn];
double dp[105][10005];
int main()
{
    int t;scanf("%d",&t);int cc=0;while(t--){
    int n;double p;scanf("%lf%d",&p,&n);for(int i=1;i<=n;i++) scanf("%d%lf",&x[i].m,&x[i].p);memset(dp,0,sizeof(dp));dp[0][0]=1;int ans=0;for(int i=1;i<=n;i++){
    for(int j=0;j<=10000;j++){
    dp[i][j]=dp[i-1][j];if(j>=x[i].m) dp[i][j]=max(dp[i][j],dp[i-1][j-x[i].m]*(1-x[i].p));if(sgn(dp[i][j]-1.0+p)>=0) ans=max(ans,j);}}printf("Case %d: %d\n",++cc,ans);}return 0;
}