HDU 1203：I NEED A OFFER！—— 0/1 背包轉化求最大錄取概率

題目大意

Speakless 手握 n 萬美元申請費，面對 m 所大學，每所學校有申請費 a_i（萬美元）與錄取概率 b_i。各校錄取獨立互不影響。請在預算內選擇申請學校，使「至少收到一份 Offer」的概率最大。輸出最大概率百分比，保留小數點後一位。

核心轉化：從「最大化至少一個成功」到「最小化全部失敗」

直接求「至少一個成功」概率需處理包含關係，極其麻煩。利用對立事件思想：

• 至少一個 Offer = 1 - 全部拒絕
• 全部拒絕概率 = ∏(1 - b_i)
• 目標轉化為：在總費用 ≤ n 的前提下，最小化 ∏(1 - b_i)

這正是經典的 0/1 背包問題：

• 容量 = n（總預算）
• 物品 = 每所大學
• 體積 = a_i（申請費）
• 價值 = 1 - b_i（拒絕概率），求最小乘積

動態規劃狀態定義與轉移

• dp[j]：花費恰好 j 萬美元時，所能達成的 最小全部拒絕概率。
• 初始化：dp[0..n] = 1.0（不申請任何學校，拒絕概率為 1）。
• 轉移方程：
  for i = 1..m
for j = n..a_i
dp[j] = min(dp[j], dp[j - a_i] * (1 - b_i))
• 答案：(1 - dp[n]) * 100，格式化輸出 %.1lf%%。

完整 AC 代碼 (C++)

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int n, m;
int a[10005];
double b[10005], dp[10005];

int main() {
    while (~scanf("%d%d", &n, &m) && (n || m)) {
        for (int i = 1; i <= m; ++i) {
            scanf("%d%lf", &a[i], &b[i]);
        }
        fill(dp, dp + n + 1, 1.0);
        for (int i = 1; i <= m; ++i) {
            double fail = 1.0 - b[i];
            for (int j = n; j >= a[i]; --j) {
                dp[j] = min(dp[j], dp[j - a[i]] * fail);
            }
        }
        printf("%.1lf%%\n", (1.0 - dp[n]) * 100);
    }
    return 0;
}

關鍵細節提醒

1. 雙重循環順序：外層遍歷物品，內層 倒序 遍歷容量，保證 0/1 背包不重複選取。
2. 概率乘積精度：使用 double 足夠，避免 float 精度不足。
3. 輸出格式：printf("%.1lf%%\n", ...) 中 %% 轉義輸出百分號。
4. 邊界情況：n=0 或 m=0 時正確輸出 0.0%。

舉例演示

輸入：10 3 / 4 0.1 / 4 0.2 / 5 0.3 / 0 0

• 選校 1+2：費用 8，拒絕概率 0.9×0.8=0.72 → 至少一個 28%
• 選校 2+3：費用 9，拒絕概率 0.8×0.7=0.56 → 至少一個 44% ✓
• 選校 1+3：費用 9，拒絕概率 0.9×0.7=0.63 → 至少一個 37%

最優策略花費 9 萬，獲得 44.0% 概率，與 Sample Output 完全吻合。