本文共 1485 字，大约阅读时间需要 4 分钟。
#include#include #include #include using namespace std;const int money_max = 1e4 + 5;const int n_max = 100 + 5;double dp[money_max];struct node{ int money; //记录可以偷多少钱 double fail; //记录失败概率 double success; //记录成功概率} rob[n_max];int t, n, sum, ans;double P_fail, P_success;int main(){ scanf("%d", & t); while(t --) { scanf("%lf %d", & P_fail, & n); P_success = 1 - P_fail; //转化成 成功概率 sum = 0; for(int i = 0; i < n; i ++) { scanf("%d %lf", & rob[i].money, & rob[i].fail); rob[i].success = 1 - rob[i].fail; //转化成 成功概率 sum += rob[i].money; //记录 总钱数 } memset(dp, 0, sizeof(dp)); dp[0] = 1; //偷0块钱 自然逃跑成功概率100% for(int i = 0; i < n; i ++) for(int j = sum; j >= rob[i].money; j --) dp[j] = max(dp[j], dp[j - rob[i].money] * rob[i].success); //状态转移方程 for(int i = sum; i >= 0; i --) { if(dp[i] >= P_success) { ans = i; break; } } printf("%d\n", ans); } return 0;}
：
有个人去抢劫银行，已知最大风险指数，想要成功逃跑，风险必须控制在小于或等于这个风险内，并且知道各银行所存的钱及各银行被抓的风险，求在成功逃跑的情况下所能抢到最多的钱是多少？
题解：
（摘自百度文库）顺着题意做非常困难，需要转换思维，把最大风险指数改成最小逃跑所需指数，各银行的被抓指数也改成能逃跑的指数pi=1-pi，因此想要成功逃跑，总逃跑指数必须大于或等于最小逃跑所需指数，因为逃跑是独立事件，所以 总逃跑指数 = 各逃跑成功指数相乘 （我理解了好久才搞懂，重要！），在dp过程中设钱的数量为背包容量的大小，dp方程： dp[j]=max(dp[j],dp[j-pe[i].mj]*pe[i].pj)。
转载地址：http://ectpi.baihongyu.com/