题目背景
有抱负的强盗罗伊看了很多美国电影，知道坏家伙通常最终会被抓到，往往是因为变得太贪心。他决定只在银行抢劫这个利润丰厚的行业工作一小段时间，然后退休到大学里的一个舒适的工作。
罗伊已经几个月来一直在评估各个银行的安全性以及它们所持有的现金数量。他想要冒一定的风险，尽可能多地抢到钱。
他的母亲奥拉已经确定了一个可以接受的被抓到的概率。她觉得如果他抢劫的银行最终的概率小于这个值，他就足够安全。
输入格式
第一行输入一个整数 T，表示案例的数量。
对于每个测试案例：
- 第一行包含一个浮点数 P 和一个整数 N P：罗伊需要保持在其以下的被抓概率 N：他计划抢劫的银行数量
- 接下来 N 行，每行包含一个整数 Mj 和一个浮点数 Pj Mj：第 j 家银行包含的金额（百万美元） Pj：抢劫该银行被抓到的概率
输出格式
对于每个测试案例，输出一行，表示在被抓到的概率低于设定限制时他可以期望得到的最大金额（以百万为单位）。
输入输出样例
输入样例
1
0.04 3
1 0.02
2 0.03
3 0.05
输出样例
6
题解
思考： 他的母亲奥拉已经确定了一个可以接受的被抓到的概率。她觉得如果他抢劫的银行最终的概率小于这个值，他就足够安全。
目标：在被抓的概率 <=P 的 获得最大利润。
f[v] : 获得价值v的最小概率。
1. 如果只有1个银行，被抓的概率为 p[1], p[1]<=P ,获得的利润val[1]
2. 如果只有2个银行，被抓的概率为 p[1](1-p[1])+(1-p[1])p[2]+p[1]*p[2]
目标修改为：不被抓的概率，>=p ,获得最大利润f[v] ，获得金额v，不被抓的最大概率。被抓的概率 （1-f[v]<=p）即为安全的。`f[v]= max(f[v],f[v-w[i]]*(1-p[i]))`
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int T,n,v[102];double P,p[102],f[10002];int main() {cin>>T;int sum=0;while (T--) {scanf("%lf%d",&P,&n);for (int i=1;i<=n;i++) scanf("%d%lf",&v[i],&p[i]),sum+=v[i];memset(f,0,sizeof(f));f[0]=1;for (int i=1;i<=n;i++)for (int j=sum;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]*(1-p[i]));while (sum>0 && 1-f[sum]>P) sum--;cout<<sum<<endl;}return 0;
}