题意:
抢银行(这个背景最爱了), 有n家银行, 每家银行抢劫被抓的概率是p[i],你认为当你被抓的概率低于P的时候是安全的。
问, 你最多能抢劫到多少money。
思路:
抽象成背包问题, 每家银行只有两种选择, 要么抢, 要么不抢。
被抓的概率有点难求, 因为还要考虑之前没有被抓。这里换成求互斥事件:不被抓的概率。
概率为权值, money为重量, 状态转移方程:
dp[i] = max(dp[i], dp[i - money[j]] * (1 - p[j]))
最后在dp[money_count]里找到一个满足概率大于P 的最大下标即可。
代码:
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MAXN 10010
20 #define MOD 1000000007
21 #define eps 1e-6
22 double dp[MAXN];
23 int w[MAXN];
24 double v[MAXN];
25 int n;
26 double p;
27 void show(int V)
28 {
29 for(int i = 0; i <= V; i ++)
30 printf(dp[i] == INF? "INF ," : "%.3lf ,", dp[i]);
31 printf("\n");
32 }
33 void ZeroOnePack(int V, int n)
34 {
35 fill(dp, dp + V + 1, 0);
36
37 dp[0] = 1.0;
38 for(int i = 0; i < n; i ++)
39 for(int j = V; j >= w[i]; j --)
40 dp[j] = max(dp[j], dp[j - w[i]] * (1 - v[i]));
41 }
42
43 int main()
44 {
45 int T;
46 int kcase = 0;
47 scanf("%d", &T);
48 while(T --)
49 {
50 int V = 0;
51 scanf("%lf %d", &p, &n);
52 for(int i = 0; i < n; i ++)
53 {
54 scanf("%d %lf", &w[i], &v[i]);
55 V += w[i];
56 }
57 ZeroOnePack(V, n);
58 int ans = 0;
59 for(int i = 0 ; i <= V; i ++)
60 if(dp[i] > (1 - p))
61 ans = max(ans, i);
62 printf("Case %d: %d\n", ++ kcase, ans);
63 }
64 return 0;
65 }