HDU 2955 Robberies：0-1 背包轉化逃脫概率最大化問題

題目重述

n 家銀行，第 i 家金額 m_i，被抓概率 p_i。選擇若干銀行搶劫，要求總被抓概率 P_total ≤ P（給定閾值）。最大化總金額。轉化：逃脫概率 q_i = 1 - p_i，總逃脫概率 ∏ q_i ≥ 1-P。取對數或直接用概率乘法作為價值。

DP 狀態

0-1 背包：dp[v] 表示總金額恰為 v 時的最大逃脫概率。初始 dp[0]=1，其餘 0。轉移：

for each bank i:
    for v = sum_m down to m_i:
        dp[v] = max(dp[v], dp[v-m_i] * q_i);

最終從大到小掃描 v，首個 dp[v] ≥ 1-P 即為答案。

C++ 代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXM = 10000;  // 總金額上限
double dp[MAXM+1];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        double P; int n; cin >> P >> n;
        P = 1 - P;  // 目標逃脫概率
        vector m(n);
        vector q(n);
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            cin >> m[i] >> q[i];
            q[i] = 1 - q[i];  // 逃脫概率
            sum += m[i];
        }
        fill(dp, dp+sum+1, 0);
        dp[0] = 1;
        for (int i = 0; i < n; ++i)
            for (int v = sum; v >= m[i]; --v)
                dp[v] = max(dp[v], dp[v-m[i]] * q[i]);
        int ans = 0;
        for (int v = sum; v >= 0; --v)
            if (dp[v] >= P) { ans = v; break; }
        cout << ans << '\n';
    }
    return 0;
}

關鍵點

• 價值為概率（乘法），需用 double 存儲，初始化為 0，dp[0]=1。
• 逆序遍歷保證 0-1 特性（每家銀行最多選一次）。
• 總金額上限 1e4，DP 陣列大小可控。

複雜度

• 時間：O(n * sum_m)。
• 空間：O(sum_m)。