前置知識

這題是 0/1 背包換個說法，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 0/1 背包：NTUCPC Guide〈背包問題〉——「每件選或不選、容量不能超」的表格定義與轉移；〈滾動 DP〉說明一維陣列為什麼容量要從大到小更新。吳邦一《AP325》第 6 章 6.2.2 的 Q-6-10「置物櫃出租」正是本題（教材 PDF 第 183 頁，前面 P-6-9 的解說就是 0/1 背包；Python 版第 6 章（II））。

簡潔題意

\(M\) 個置物櫃已租給 \(N\) 位客人，第 \(i\) 位借了 \(x_i\) 個（\(\sum x_i \le M\)）。新客人要 \(S\) 個空櫃，你可以取消某些客人的租借（一位客人要嘛全取消、要嘛全保留），求最少要取消幾個櫃子才能湊出至少 \(S\) 個空櫃；原本空櫃就夠就是 \(0\)（\(M \le 10^5\)、\(S \le M\)、\(N \le 100\)；APCS 逐筆給分）。

反過來想：不是「取消最少」，是「保留最多」

取消的櫃子＝全部借出的 − 保留的，全部借出的是定值，所以取消最少＝保留最多。保留有什麼限制？新客人要 \(S\) 個，所以保留的總數不能超過 \(M - S\)（圖 1）。於是題目變成：

\(N\) 位客人，每位「留」或「不留」，留下的總櫃數不能超過 \(M - S\)，問最多能留幾個。

這就是 0/1 背包：容量 \(M - S\)，每位客人是一件「重量 \(x_i\)、價值也是 \(x_i\)」的物品。

填表：keep[c] ＝ 容量 c 裡最多能留幾個櫃子

用一維陣列 keep[c] 記「容量不超過 \(c\) 時最多能留的櫃數」，一開始全是 \(0\)。一位一位客人加進來：對每個容量 \(c \ge x_i\)，keep[c] = max(keep[c], keep[c - x_i] + x_i)——不留他就維持原值，留他就從「少 \(x_i\) 的容量」那格接上來。\(c\) 要從大到小跑：由小到大的話 keep[c - x_i] 已經是「加了這位客人之後」的值，同一位客人會被留兩次。

最後答案＝全部借出的總數 \(- \text{keep}[M - S]\)。原本空櫃就夠（\(M - \sum x_i \ge S\)）時，所有客人加起來都放得進容量，keep[M - S] 就是全部借出的總數，答案自然是 \(0\)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m, s, n;
    cin >> m >> s >> n;
    vector<int> x(n);
    int rented = 0;                                  // 目前借出的總數
    for (int i = 0; i < n; i++) {
        cin >> x[i];
        rented += x[i];
    }

    int capacity = m - s;                            // 既有客人最多只能留這麼多
    vector<int> keep(capacity + 1, 0);               // keep[c]：容量 c 裡最多能留幾個櫃子
    for (int i = 0; i < n; i++)
        for (int c = capacity; c >= x[i]; c--)       // 從大到小：每位客人只能留一次
            keep[c] = max(keep[c], keep[c - x[i]] + x[i]);

    cout << rented - keep[capacity] << '\n';
    return 0;
}

\(N \le 100\)、容量 \(\le 10^5\)，最多 \(10^7\) 次更新。借 \(0\) 個的客人留不留都一樣，迴圈裡 c >= 0 全跑一遍也不會出錯。

測過再交：範例裡沒有空櫃、也沒有「剛好湊滿」

範例的 \(\sum x_i = 20 = M\)，一個空櫃都沒有。沒蓋到的：原本空櫃就夠、剛好能留滿 \(M - S\)、只有一位客人、\(S = M\)（全部都要取消）。

五筆都親眼看過正確，這題就穩了。