本文共 968 字，大约阅读时间需要 3 分钟。

题意

Roy去抢银行，每个银行都有一定的财富和被抓的风险，在不超过Roy可承受的风险内最大可以抢多少钱？

AC

• 01背包
  首先会想到把被抓概率作为背包容量，把财富作为价值，因为概率为小数存在精度问题而且概率之间不是简单相加而是累乘（每个时间独立），这是需要将财富作为背包容量，把概率作为价值，要使被转概率小，则需要逃跑概率尽可能大。

using namespace std;int inf = 0x3f3f3f3f;int main(){#ifndef ONLINE_JUDGE    freopen("in.txt", "r", stdin);#endif    int t;    cin >> t;    while (t--) {        double p0, p[105];        int n, sum = 0, m[105];        double dp[10004];         cin >> p0 >> n;        for (int i = 0; i < n; ++i) {            cin >> m[i] >> p[i];            sum += m[i];        }        // 初始化所有的逃跑概率为零,dp[0] = 1        mem(dp, 0);        dp[0] = 1;        for (int i = 0; i < n; ++i) {            for (int j = sum; j >= m[i]; --j) {                // 计算拿和不拿 最大的逃跑概率                dp[j] = max(dp[j], dp[j - m[i]] * (1 - p[i]));            }        }        for (int i = sum; i >= 0; --i) {            if (1 - dp[i] < p0) {                cout << i << endl;                break;            }        }    }    return 0;}

转载地址：http://pkprf.baihongyu.com/