HDU 2955 Robberies：01 背包變體求最大搶劫金額

HDU 2955 Robberies：概率約束下的 01 背包

題目大意：Roy 計劃搶劫 N (≤100) 家銀行，第 i 家有 M_i 百萬美元，被抓概率 P_i。母親容忍總被抓概率 < P。求在總被抓概率 < P 前提下，最大期望搶劫金額（百萬美元）。概率獨立，搶劫後銀行破產。

關鍵轉化：安全概率 DP

「被抓概率 < P」等價於「安全概率 > 1-P」。
安全概率 = ∏ (1 - P_i)（選中的銀行）。
目標：最大化 Σ M_i，滿足 ∏ (1 - P_i) > 1-P。
取對數會變加法，但題目要求精確比較，直接用 DP 維護最大安全概率。
定義 dp[v] = 價值恰為 v 時的最大安全概率。初始 dp[0] = 1。
01 背包轉移：dp[v] = max(dp[v], dp[v - M_i] * (1 - P_i))。
最後從大到小找最大 v 使 dp[v] > 1-P。

核心代碼

double dp[10001]; // 最大總金額 100*100 = 10000
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        double P; int N;
        scanf("%lf%d", &P, &N);
        double safeLimit = 1 - P;
        memset(dp, 0, sizeof(dp));
        dp[0] = 1.0;
        for (int i = 0; i < N; i++) {
            int M; double p;
            scanf("%d%lf", &M, &p);
            double safe = 1 - p;
            for (int v = 10000; v >= M; v--)
                if (dp[v] < dp[v-M] * safe)
                    dp[v] = dp[v-M] * safe;
        }
        for (int v = 10000; v >= 0; v--)
            if (dp[v] > safeLimit) { printf("%d\n", v); break; }
    }
    return 0;
}

細節說明

• 總金額上限 100*100=10000，DP 數組大小 10001 足夠。
• 概率乘法用 double，精度足夠。
• 初始 dp[0]=1 表示不搶劫任何銀行時安全概率為 1。
• 逆序更新 v 保證 01 背包每項只用一次。