Try   HackMD

APCS實作題2018年：置物櫃分配

第1版：2023年9月9日
第2版：2024年12月21日
作者：王一哲
題目來源：107年6月實作題
ZeroJudge 題目連結


題目

問題描述

你是個櫃子租借商，總共擁有

M 個櫃子。現在這
M 個櫃子分別被
N 個人借用，借用量分別為
(x0,x1,x2,…,xN−1) 個櫃子，其中
x0+x1+x2+⋯+xN−1≤M。

現在你想要使用

S 個空櫃子，在被借用的櫃子只能夠全退或全不退之下，最少需要請這 N 個人退還多少櫃子？也就是當有一個人借用10個櫃子時，不能夠只請他退還5個櫃子。

舉例來說，對於

M=20 個櫃子，現在分別被5個人借用 (1, 7, 2, 8, 2) 個櫃子，在需要使用
S=14 個櫃子之下，最少需要請他們退還
7+8=15 個櫃子。

輸入格式

第一行有三個正整數

M、
S、
N，分別代表櫃子總數
M、想要使用的櫃子數
S、借用人數
N。
M≤100000,     S≤M,     N≤100000

第二行有

N 個非負整數
x0,x1,x2,…,xN−1，代表每個人所借用的櫃子數量。
其中
x0+x1+x2+⋯+xN−1≤M。

輸出格式

最少需要請這

N 個人退還的櫃子總數

範例：輸入

20 14 5
1 7 2 8 2

範例：正確輸出

15

Python 程式碼

寫法1，使用 bitset

以下的程式碼主要參考這個網頁，使用 bitset 求指定資料可能的總合主要參考 LeetCode 416. Partition Equal Subset Sum 討論區 C++ Bitset Solution。其中最難理解的部分是第3、4行，以 ZeroJudge 網頁的範例來說明，由於已借出的格子數為

1,7,2,8,2，可能的總合有
1,2,3,4,5,7,8,9,10,11,12,13,15,16,17,18,19,20，如果 possSum 先設定為1，先將 possSum 向左移1位再與原本的值取 or 運算，其2進位值為

0b11

這代表 possSum 可能為 1。接下來再向左平移7位並與原本的值取 or 運算，其2進位值為

0b110000011

這代表 possSum 可能為 1、7、8，也就是看2進位值中哪幾個位數是1，就代表總合可能是這幾個位數。接下再代入 2、8、2 的結果依序為

0b11110001111
0b1111000111110001111
0b111111011111110111111

再由最後一位向前搜尋字串1，如果 target 對應的位數不是1，再繼續向前找，找到的位數就是答案。

於 ZeroJudge 測試結果，最長運算時間約為 44 ms，使用記憶體最多約為 3.5 MB，通過測試。



















def solve(array, tar):
    possSum = 1
    for x in array:
        possSum |= (possSum << x)
    s = bin(possSum)[2:]
    for i in range(len(s)):
        if i >= tar and s[len(s)-i-1] == '1':
            return i

M, S, N = map(int, input().split())
data = list(map(int, input().split()))
left = M - sum(data)  # 目前剩下的空格數
target = S - left     # 需要歸還的格子數量

if target <= 0:       # 如果 target <= 0 不需要歸還格子，印出0
    print(0)
else:
    print(solve(data, target))

寫法2，使用二維陣列及 DP

於 ZeroJudge 測試結果，有6筆測資需要的記憶體爆掉。


















M, S, N = map(int, input().split())  # M 個櫃子，需要 S 個櫃子，有 N 個人借用
xs = list(map(int, input().split()))  # 每個客戶租用的格子數量
ans = M  # 答案預設為 M
goal = S - (M - sum(xs))  # 目標需要收回的格子數量
if goal <= 0: ans = 0  # 不需要歸還任何櫃子，答案為 0
else:  # 需要歸還櫃子
    dp = [[0]*(M+1) for _ in range(N+1)]  # dp[i][j] 為第 i 個客戶累計收回 j 個格子
    if xs[0] >= goal: ans = min(ans, xs[0])  # 更新 ans，取較小的值
    for j in range(xs[0], M+1): dp[1][j] = xs[0]  # 處理第 1 項
    for i, x in enumerate(xs[1:], start=2):  # 處理第 2 ~ n 項
        for j in range(1, M+1):  # 依序檢查收回格子數量 1 ~ M
            if x > j: dp[i][j] = dp[i-1][j]  # 如果 x 大於 j，沒有回數更多的數量，與檢查第 i-1 個客戶時相同
            else:  # 回數更多的數量，取檢查第 i-1 個客戶時的數量與加上 x 時較大者
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-x] + x)
                if dp[i][j] >= goal: ans = min(ans, dp[i][j])  # 大於等於目標，更新 ans，取較小的值

print(ans)

寫法3，使用滾動陣列及 DP

於 ZeroJudge 測試結果，最後一筆測資超時。



















M, S, N = map(int, input().split())  # M 個櫃子，需要 S 個櫃子，有 N 個人借用
xs = list(map(int, input().split()))  # 每個客戶租用的格子數量
ans = M  # 答案預設為 M
goal = S - (M - sum(xs))  # 目標需要收回的格子數量
if goal <= 0: ans = 0  # 不需要歸還任何櫃子，答案為 0
else:  # 需要歸還櫃子
    d, p = [0]*(M+1), [0]*(M+1)  # 為第 i 個客戶累計收回 j 個格子
    if xs[0] >= goal: ans = min(ans, xs[0])  # 更新 ans，取較小的值
    for j in range(xs[0], M+1): p[j] = xs[0]  # 處理第 1 項
    for x in xs[1:]:  # 處理第 2 ~ n 項
        for j in range(1, M+1):  # 依序檢查收回格子數量 1 ~ M
            if x > j: d[j] = p[j]  # 如果 x 大於 j，沒有回數更多的數量，與檢查第 i-1 個客戶時相同
            else:  # 回數更多的數量，取檢查第 i-1 個客戶時的數量與加上 x 時較大者
                d[j] = max(p[j], p[j-x] + x)
                if d[j] >= goal: ans = min(ans, d[j])  # 大於等於目標，更新 ans，取較小的值
        d, p = p, d  # 交換資料

print(ans)



C++ 程式碼

寫法1，使用 bitset

於 ZeroJudge 測試結果，最長運算時間約為 7 ms，使用記憶體最多約為 704 kB，通過測試。




































#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

int solve(vector<int> array, int tar);

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int M, S, N; cin >> M >> S >> N;
    vector<int> data (N, 0);
    int total = 0;
    for(int i=0; i<N; i++) {
        cin >> data[i];
        total += data[i];
    }
    int left = M - total;  // 目前剩下的空格數
    int target = S - left; // 需要歸還的格子數量
    if (target <= 0)       // 如果 target <= 0 不需要歸還格子，印出0
        cout << 0 << "\n";
    else
        cout << solve(data, target) << "\n";
    return 0;
}

int solve(vector<int> array, int tar) {
    bitset<1000000> possSum;
    possSum[0] = 1;
    for(auto x : array) 
        possSum |= (possSum << x);
    for(int i=tar; i<1000000; i++) {
        if (possSum[i] == 1) return i;
    }
    return 0;
}

寫法2，使用二維陣列及 DP

於 ZeroJudge 測試結果，最長運算時間約為 39 ms，使用記憶體最多約為 39.4 MB，通過測試。

































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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int M, S, N, isum = 0; cin >> M >> S >> N;  // M 個櫃子，需要 S 個櫃子，有 N 個人借用
    vector<int> xs (N, 0);  // 每個客戶租用的格子數量
    for(int i=0, x; i<N; i++) {
        cin >> x; xs[i] = x; isum += x;  // isum 為已出借的櫃子數量
    }
    int ans = M, goal = S - (M - isum);  // 答案預設為 M，目標需要收回的格子數量
    if (goal <= 0) ans = 0;  // 不需要歸還任何櫃子，答案為 0
    else {  // 需要歸還櫃子
        vector<vector<int>> dp (N+1, vector<int> (M+1, 0));  // dp[i][j] 為第 i 個客戶累計收回 j 個格子
        if (xs[0] >= goal) ans = min(ans, xs[0]);  // 更新 ans，取較小的值
        for(int j=xs[0]; j<=M; j++) dp[1][j] = xs[0];  // 處理第 1 項
        for(int i=2; i<=N; i++) {  // 處理第 2 ~ n 項
            for(int j=1, x; j<=M; j++) {  // 依序檢查收回格子數量 1 ~ M
                x = xs[i-1];  // 目前在檢查的格子數量
                if (x > j) dp[i][j] = dp[i-1][j];  // 如果 x 大於 j，沒有回數更多的數量，與檢查第 i-1 個客戶時相同
                else {  // 回數更多的數量，取檢查第 i-1 個客戶時的數量與加上 x 時較大者
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-x] + x);
                    if (dp[i][j] >= goal) ans = min(ans, dp[i][j]);  // 大於等於目標，更新 ans，取較小的值
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

寫法3，使用滾動陣列及 DP

於 ZeroJudge 測試結果，最長運算時間約為 17 ms，使用記憶體最多約為 1.1 MB，通過測試。


































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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int M, S, N, isum = 0; cin >> M >> S >> N;  // M 個櫃子，需要 S 個櫃子，有 N 個人借用
    vector<int> xs (N, 0);  // 每個客戶租用的格子數量
    for(int i=0, x; i<N; i++) {
        cin >> x; xs[i] = x; isum += x;  // isum 為已出借的櫃子數量
    }
    int ans = M, goal = S - (M - isum);  // 答案預設為 M，目標需要收回的格子數量
    if (goal <= 0) ans = 0;  // 不需要歸還任何櫃子，答案為 0
    else {  // 需要歸還櫃子
        vector<int> d (M+1, 0), p (M+1, 0);  // 為第 i 個客戶累計收回 j 個格子
        if (xs[0] >= goal) ans = min(ans, xs[0]);  // 更新 ans，取較小的值
        for(int j=xs[0]; j<=M; j++) p[j] = xs[0];  // 處理第 1 項
        for(int i=2; i<=N; i++) {  // 處理第 2 ~ n 項
            for(int j=1, x; j<=M; j++) {  // 依序檢查收回格子數量 1 ~ M
                x = xs[i-1];  // 目前在檢查的格子數量
                if (x > j) d[j] = p[j];  // 如果 x 大於 j，沒有回數更多的數量，與檢查第 i-1 個客戶時相同
                else {  // 回數更多的數量，取檢查第 i-1 個客戶時的數量與加上 x 時較大者
                    d[j] = max(p[j], p[j-x] + x);
                    if (d[j] >= goal) ans = min(ans, d[j]);  // 大於等於目標，更新 ans，取較小的值
                }
            }
            swap(d, p);  // 交換資料
        }
    }
    cout << ans << "\n";
    return 0;
}



tags:APCS、Python、C++
Last changed by 
 
Yi-Zhe Wang
0
315

Read more

Python 及 C++ 遍歷字串

作者：王一哲日期：2023年7月29日

May 10, 2025
Python 及 C++ 字串處理

作者：王一哲日期：2023年7月29日

May 9, 2025
C++ 陣列 array 及 STL vector

要先引入函式庫，函式庫的官方說明書在此 cplusplus.com std::deque。

May 3, 2025
C++ 基礎語法練習題：Unit-3 比較運算、邏輯運算 、if 判斷、switch 判斷

講義不是我寫的，原文連結為 Yui Huang 演算法學習筆記：C++ 基礎語法 我只是將自己寫的練習題程式碼記錄下來。 最後更新日期：2024年11月9日

Apr 29, 2025
Read more from Yi-Zhe Wang
Published on HackMD