问题
tab: English
## Robberies
**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 44678 Accepted Submission(s): 15836
**
Problem Description
The aspiring Roy the Robber has seen a lot of American movies, and knows that the bad guys usually gets caught in the end, often because they become too greedy. He has decided to work in the lucrative business of bank robbery only for a short while, before retiring to a comfortable job at a university.
For a few months now, Roy has been assessing the security of various banks and the amount of cash they hold. He wants to make a calculated risk, and grab as much money as possible.
His mother, Ola, has decided upon a tolerable probability of getting caught. She feels that he is safe enough if the banks he robs together give a probability less than this.
Input
The first line of input gives T, the number of cases. For each scenario, the first line of input gives a floating point number P, the probability Roy needs to be below, and an integer N, the number of banks he has plans for. Then follow N lines, where line j gives an integer Mj and a floating point number Pj.
Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj.
Output
For each test case, output a line with the maximum number of millions he can expect to get while the probability of getting caught is less than the limit set.
Notes and Constraints
0 < T <= 100
0.0 <= P <= 1.0
0 < N <= 100
0 < Mj <= 100
0.0 <= Pj <= 1.0
A bank goes bankrupt if it is robbed, and you may assume that all probabilities are independent as the police have very low funds.
Sample Input
```
3
0.04 3
1 0.02
2 0.03
3 0.05
0.06 3
2 0.03
2 0.03
3 0.05
0.10 3
1 0.03
2 0.02
3 0.05
```
Sample Output
```
2
4
6
```
Source
[IDI Open 2009](https://acm.hdu.edu.cn/search.php?field=problem&key=IDI+Open+2009&source=1&searchmode=source)
[Statistic](https://acm.hdu.edu.cn/statistic.php?pid=2955) | [Submit](https://acm.hdu.edu.cn/submit.php?pid=2955) | [Discuss](https://acm.hdu.edu.cn/discuss/problem/list.php?problemid=2955) | [Note](https://acm.hdu.edu.cn/note/note.php?pid=2955)
tab: 中文
## 抢劫
**时间限制：2000/1000 MS (Java/其他) 内存限制：32768/32768 K (Java/其他)
提交总数：44678 已接受的提交：15836
**
问题描述
雄心勃勃的强盗罗伊看过很多美国电影，他知道坏人通常最终都会被抓住，这往往是因为他们太贪婪了。他决定先在利润丰厚的银行抢劫行业干一小段日子，然后再退休去大学找一份舒适的工作。
几个月来，罗伊一直在评估各家银行的安保措施和它们持有的现金数量。他想冒险一试，尽可能多地抢劫。
他的母亲奥拉已经确定了一个可以接受的被抓概率。她认为，只要他抢劫的银行叠加的概率低于这个数字，他就足够安全了。
输入
输入的第一行给出 T，即案例数量。对于每种情景，第一行输入一个浮点数 P，表示 Roy 需要低于该概率的概率，以及一个整数 N，表示他计划抢劫的银行数量。接下来是 N 行，其中第 j 行给出一个整数 Mj 和一个浮点数 Pj 。
银行 j 有 Mj 百万，抢劫被抓的概率为 Pj 。
输出
对于每个测试用例，输出一行，表示在被抓住的概率小于设定的极限的情况下，他可以期望获得的最大数百万数。
注意事项和约束
0 < T <= 100
0.0 <= P <= 1.0
0 < N <= 100
0 < Mj <= 100
0.0 <= Pj <= 1.0
如果银行被抢劫，它就会破产，你可以假设所有概率都是独立的，因为警察的资金非常低。
示例输入
```
3
0.04 3
1 0.02
2 0.03
3 0.05
0.06 3
2 0.03
2 0.03
3 0.05
0.10 3
1 0.03
2 0.02
3 0.05
```
示例输出
```
2
4
6
```
来源
[2009年IDI公开赛](https://acm.hdu.edu.cn/search.php?field=problem&key=IDI+Open+2009&source=1&searchmode=source)
[统计](https://acm.hdu.edu.cn/statistic.php?pid=2955) | [提交](https://acm.hdu.edu.cn/submit.php?pid=2955) | [讨论](https://acm.hdu.edu.cn/discuss/problem/list.php?problemid=2955) | [备注](https://acm.hdu.edu.cn/note/note.php?pid=2955)个人解法
- 一开始以为测试用例的概率都是小数点后两位，所以可以将概率乘以 100 转为整数，这样就可以直接使用整数的 0-1 背包算法
- 示例通过，submit 不通过，估计测试用例里有小数点后两位的概率，这种方法行不通
- 叠加概率不是直接相加，而是需要计算组合概率
- 例如，两个银行的概率分别为 0.02 和 0.03，那么组合概率应该是 1 - (1 - 0.02) * (1 - 0.03) = 0.0494
- 暴力解法：枚举所有银行组合，计算组合概率和金额，选择组合概率小于 P 的最大金额，SC: O(2^N)
- 二进制枚举的方法效率一般没递归高，而且还占内存，所以还是用递归实现。
- 进阶解法：正常 0-1 背包的思路是枚举 0~P 概率下能抢到的最大金额，但这里概率不是整数，通过乘系数转成整数的方法前面试过不行，这里我们可以换个思路：
- 由于金额数不是很大，我们可以枚举 0~最大可能金额下的不被抓的最大概率，最后倒叙遍历金额，找到不超过给定的风险数，就是最大能抢到的金额。
基于这个思路的启发，想到如果原背包问题的价值是整数，重量和背包容量都是浮点数的情况，或者价值比较小，重量比较大的情况，也可以转换思维，通过枚举 0~最大可能价值下的最小重量，最后倒叙遍历重量，找到不超过给定的容量，就是最大能装的价值。
暴力解法：回溯/dfs
/** 暴力解法: 回溯遍历,dfs */
int _solve_v1(vector<int>& m, vector<float>& p, float P, int i, float pp) {
// pp: 被抓概率
if (i < 0) {
return 0;
}
// 不抢当前银行
int no = _solve_v1(m, p, P, i - 1, pp);
// 尝试抢当前银行
double new_prob = 1.0 - (1.0 - pp) * (1.0 - p[i]);
int yes = -1; // 表示无效方案
if (new_prob < P) { // 只有概率允许时才抢
yes = _solve_v1(m, p, P, i - 1, new_prob) + m[i];
}
return max(no, yes); // max会自动处理-1的情况
}
int solve_v1(vector<int>& m, vector<float>& p, float P) {
return _solve_v1(m, p, P, m.size() - 1, 0.f);
}进阶解法
/** 进阶思路：0-1背包枚举0~最大可能金额下最小被抓概率，后倒序遍历找出最大金额 */
int solve_v2(vector<int>& m, vector<float>& p, float P) {
int M = accumulate(m.begin(), m.end(), 0);
vector<float> dp(M + 1, 1.f); // 枚举抢指定金额情况下的被抓概率，1可以表示不可能的金额情况
dp[0] = 0.f; // 不抢一定不被抓
for (int i = 0; i < m.size(); i++) {
for (int j = M; j > 0; j--) {
if (j >= m[i]) {
dp[j] = min(dp[j], 1 - (1 - dp[j - m[i]]) * (1 - p[i]));
}
}
}
int i = M;
for (; i >= 0; i--) {
if (dp[i] < P) {
break;
}
}
return i;
}