题意大概是一个小哥要去抢银行，他列出了几个银行的价值和被抓概率，然后定了一个最高被抓概率，求最多可以抢多少价值的东西。
一开始想成是被抓概率简单叠加了，写了个简单的背包就直接提交，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;
} |
Technorati
Tags: 动态规划