题目链接
题目描述：
Robber想要抢银行，每个银行的钱数为mj，抢这个银行被抓的概率为pj，在被抓概率小于 p 的情况下，求最大抢劫金额。
题解：
题目中给的是抢劫每个银行被抓的概率，设
p
1
,
p
2
,
.
.
.
p
n
p_1, p_2, ...p_n
p1,p2,...pn ，由概率论知识我们可知
¬
p
1
∗
¬
p
2
∗
.
.
.
∗
¬
p
n
¬p_1*¬p_2*...*¬p_n
¬p1∗¬p2∗...∗¬pn 为不被抓的概率，显然，如果概率不为小数，我们可以把 (1 - p) 作为容量进行 0/1 背包，但概率是小数，因此这样不可行。所以我们可以转变一下思维，将
s
u
m
=
∑
m
j
sum = ∑mj
sum=∑mj 作为容量，以不被抓的概率作为价值进行 0/1 背包，最终将 dp[i] 从 sum 到 0 遍历，找到一个被抓概率(1 - 不被抓概率)小于 p 的值即为答案，状态转移方程为：
d
p
[
j
]
=
m
a
x
(
d
p
[
j
]
,
d
p
[
j
−
m
j
[
i
]
]
∗
(
1
−
p
j
[
i
]
)
)
dp[j] = max(dp[j], dp[j - mj[i]] * (1 - pj[i]))
dp[j]=max(dp[j],dp[j−mj[i]]∗(1−pj[i]))
AC Codes：
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <deque>
#include <list>
#include <iomanip>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std
;
typedef long long ll
;
const int N
= 1e4 + 6, M
= 1e9 + 7, INF
= 0x3f3f3f3f;
int mj
[105];
double dp
[N
], pj
[105];
int main() {
ios
::sync_with_stdio(false);
cin
.tie(0), cout
.tie(0);
int T
;
cin
>> T
;
while (T
--) {
double p
;
int n
;
cin
>> p
>> n
;
int sum
= 0;
for (int i
= 1; i
<= n
; i
++)
cin
>> mj
[i
] >> pj
[i
];
memset(dp
, 0, sizeof dp
);
dp
[0] = 1;
for (int i
= 1; i
<= n
; i
++) {
sum
+= mj
[i
];
for (int j
= sum
; j
>= mj
[i
]; j
--)
dp
[j
] = max(dp
[j
], dp
[j
- mj
[i
]] * (1 - pj
[i
]));
}
for (int i
= sum
; i
>= 0; i
--) {
if (1 - dp
[i
] < p
) {
cout
<< i
<< '\n';
break;
}
}
}
return 0;
}
