HDU 2955 Robberies：銀行搶劫問題的 0/1 背包概率 DP 解法

HDU 2955 Robberies：銀行搶劫問題的 0/1 背包概率 DP 解法

問題描述

劫匪 Roy 計劃搶劫 N 家銀行，每家有金額 Mj 和被抓概率 Pj。母親設定容忍總被抓概率 P。求在總被抓概率 < P 的前提下，最大期望搶劫金額。

關鍵轉化：獨立事件同時發生概率 = 概率乘積。
「不被抓概率」= 1 - 「被抓概率」。
目標：選擇子集使 ∏(1-Pj) > 1-P，最大化 ∑Mj。

動態規劃模型

• 狀態：dp[v] 表示搶到金額 v 時的最大「不被抓概率」
• 初始化：dp[0] = 1（不搶任何銀行，安全概率 100%）
• 轉移：對每家銀行，從大到小枚舉金額
  dp[v] = max(dp[v], dp[v-Mj] * (1-Pj))
• 答案：從總金額向下找第一個 dp[v] > 1-P 的 v

複雜度分析

N ≤ 100，Mj ≤ 100，總金額 ≤ 10000。
時間 O(N × 總金額) ≈ 10⁶，空間 O(總金額) ≈ 10⁴，極其高效。

完整 AC 代碼

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 10005
int va[N];
double c[N], dp[N];

int main() {
    int t, n, i;
    double p;
    scanf("%d", &t);
    while (t--) {
        int sum = 0;
        scanf("%lf%d", &p, &n);
        p = 1 - p; // 不被抓概率閾值
        for (i = 0; i < n; i++) {
            scanf("%d%lf", &va[i], &c[i]);
            sum += va[i];
        }
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (i = 0; i < n; i++)
            for (int v = sum; v >= va[i]; v--)
                dp[v] = max(dp[v], dp[v - va[i]] * (1 - c[i]));
        for (i = sum; i >= 0; i--)
            if (dp[i] - p > 1e-7) break;
        printf("%d\n", i);
    }
    return 0;
}

核心技巧總結

1. 概率乘積轉為對數可避免精度問題，但本題直接乘積精度足夠
2. 0/1 背包逆序枚舉保證每家銀行只用一次
3. 最終從大到小掃描 dp 數組找答案