题意： 小A要去抢劫银行，但是抢银行是有风险的，因此给出一个float值P，当被抓的概率<=p，他妈妈才让他去冒险。
给出一个n，接下来n行，分别给出一个Mj和Pj，表示第j个银行所拥有的钱，以及抢劫该银行被抓的可能性。
注意：抢劫各个银行被抓的可能是独立事件！
思路： 由于被抓的可能性float型，而且不仅仅只有两位，float型精度一般小数点后6-7位，
假若将被捕可能性看做容量，开10^6的数组，WA；开10^7的数组，MLE。
因此若从一般的角度，即将被捕可能性转化成整数，看做容量，将抢劫的钱看作价值，是行不通的。
而且这样求被捕的概率也比较复杂。
这题的解法确实神！
将银行的钱数看做容量，对应的价值是每个银行不被捕的概率，这样我们就将题目转化成求最大的不被捕的概率值（但并不是求这个）。
用dp[j]表示偷到的钱为 j 时不被抓的概率，则状态转移方程为：
dp[j] = max(dp[j] , dp[j-money[i]] * pro[i]);
money[i]为第i个银行的钱，pro[i]=1-pi，即不被抓的概率。
由于是独立事件，所以要用累乘。
初始条件：dp[0]=1,dp[i]=0。
最终通过从总钱数递减找到第一个大于等于期望的不被捕概率(1-p)的背包，即为不被逮捕的所能抢到的最大钱数。
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm> using namespace std;
const int maxn=;
const int maxv=;
float dp[maxv]; //求最大的不被抓概率
float p; //被抓的概率要<=p
int n;
int sum; //银行的总钱数
int money[maxn];
float prob[maxn]; int main()
{
int t,val;
float pj;
scanf("%d",&t);
while(t--){
scanf("%f%d",&p,&n);
sum=;
for(int i=;i<=n;i++){
scanf("%d%f",&val,&pj);
sum+=val;
money[i]=val; //将银行里的钱当成容量
prob[i]=-pj; //将不被抓的可能性当成价值
}
memset(dp,,sizeof(dp));
dp[]=;
for(int i=;i<=n;i++){
for(int j=sum;j>=money[i];j--){
dp[j]=max(dp[j],dp[j-money[i]]*prob[i]);
}
}
int ans=; //别忘了初始为0
for(int i=sum;i>=;i--){
if(dp[i]>=-p){
ans=i;
break;
}
}
printf("%d\n",ans);
}
return ;
}