题意大概是一个小哥要去抢银行，他列出了几个银行的价值和被抓概率，然后定了一个最高被抓概率，求最多可以抢多少价值的东西。
一开始想成是被抓概率简单叠加了，写了个简单的背包就直接提交，WA..o(╯□╰)o
不过确实是背包问题，不过求的值是逃跑概率，然后只要在能逃跑的范围内找最大价值就好了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 |
#include <cstdio>#include <cstring>#include <algorithm>using
namespace
std;double
f[10001],p[150],P;int
m[150];int
main() { int
T,n; scanf("%d",&T); while(T--) { int
sum = 0; memset(f,0,sizeof(f)); scanf("%lf%d",&P,&n); for(int
i = 1;i <= n;i++) { scanf("%d%lf",&m[i],&p[i]); sum += m[i]; } for(int
i = 1;i <= sum;i++) f[i] = 0; f[0] = 1; for(int
i = 1;i <= n;i++) { for(int
j = sum;j >= m[i];j--) { f[j] = max(f[j],f[j - m[i]] * (1 - p[i])); } } for(int
i = sum;i >= 0;i--) if(f[i] >= (1 - P)) { printf("%d\n",i); break; } } return
0;} |
原文：http://www.cnblogs.com/rolight/p/3531078.html