HDU 1203 I NEED A OFFER! - 01 背包變體求最大錄取概率

題目大意

Speakless 有 n 萬美元 (n ≤ 10000)，m 所大學 (m ≤ 10000)。第 i 校申請費 a_i 萬美元，錄取概率 b_i。各校獨立。求至少獲得一份 Offer 的最大概率 (百分比，保留 1 位小數)。

轉化：最小化「全軍覆沒」概率

設選擇集合 S，至少一份 Offer 概率 = 1 - ∏_{i∈S} (1 - b_i)。
最大化該值 ⇔ 最小化 ∏_{i∈S} (1 - b_i) (全拒絕概率)。

01 背包 DP

• 狀態：dp[j] = 花費恰好 j 萬美元 (或 ≤ j) 可達成的最小全拒絕概率。
• 初始化：dp[0..n] = 1 (不申請任何學校，全拒絕概率 = 1)。
• 轉移 (倒序枚舉費用，01 背包)：

  
  for each school i:
      for j = n down to cost[i]:
          dp[j] = min(dp[j], dp[j - cost[i]] * (1 - p[i]));
  

• 答案：(1 - dp[n]) * 100%。

關鍵細節

1. 倒序枚舉：保證每所學校至多選一次 (01 背包)。
2. 概率乘法：獨立事件全拒絕概率為乘積，DP 值單調遞減。
3. 雙精度：double 足夠，輸出 printf("%.1f%%\n", (1-dp[n])*100) (注意 %% 輸出 % 符號)。
4. 費用上限：n ≤ 10000，dp 陣列大小 10005 即可。

完整代碼

#include 
#include 
#include 
using namespace std;

const int MAXN = 10005;
double dp[MAXN], p[MAXN];
int cost[MAXN];

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m), n || m) {
        fill(dp, dp + n + 1, 1.0); // 初始化為 1
        for (int i = 0; i < m; ++i)
            scanf("%d%lf", &cost[i], &p[i]);
        for (int i = 0; i < m; ++i)
            for (int j = n; j >= cost[i]; --j)
                dp[j] = min(dp[j], dp[j - cost[i]] * (1 - p[i]));
        printf("%.1f%%\n", (1 - dp[n]) * 100);
    }
    return 0;
}

複雜度

• 時間：O(m × n) ≤ 10⁸，C++ 優化後 ~0.5s 內通過。
• 空間：O(n) 滾動陣列。

變體延伸

• 若需輸出具體選擇方案，需加 pre 陣列記錄決策路徑。
• 若費用極大但學校數小，可改「概率為狀態、費用為值」的 DP。