# APCS實作題2018年：置物櫃分配
> 第1版：2023年9月9日
> 第2版：2024年12月21日
> 作者：王一哲
> 題目來源：107年6月實作題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=e465)
<br />
## 題目
### 問題描述
你是個櫃子租借商，總共擁有 $M$ 個櫃子。現在這 $M$ 個櫃子分別被 $N$ 個人借用，借用量分別為 $(x_0, x_1, x_2, \dots, x_{N-1})$ 個櫃子，其中 $x_0 + x_1 + x_2 + \dots + x_{N-1} \leq M$。
現在你想要使用 $S$ 個空櫃子，在被借用的櫃子只能夠**全退**或**全不退**之下，最少需要請這 N 個人退還多少櫃子？也就是當有一個人借用10個櫃子時，不能夠只請他退還5個櫃子。
舉例來說，對於 $M = 20$ 個櫃子，現在分別被5個人借用 (1, 7, 2, 8, 2) 個櫃子，在需要使用 $S = 14$ 個櫃子之下，最少需要請他們退還 $7 + 8 = 15$ 個櫃子。
<br />
### 輸入格式
第一行有三個正整數 $M$、$S$、$N$，分別代表櫃子總數 $M$、想要使用的櫃子數 $S$、借用人數 $N$。
$$
M \leq 100000, ~~~~~ S \leq M, ~~~~~ N \leq 100000
$$
第二行有 $N$ 個非負整數 $x_0, x_1, x_2, \dots, x_{N-1}$，代表每個人所借用的櫃子數量。
其中 $x_0 + x_1 + x_2 + \dots + x_{N-1} \leq M$。
<br />
### 輸出格式
最少需要請這 $N$ 個人退還的櫃子總數
<br />
### 範例：輸入
```
20 14 5
1 7 2 8 2
```
### 範例：正確輸出
```
15
```
<br />
## Python 程式碼
### 寫法1，使用 bitset
以下的程式碼主要參考[這個網頁](https://david-chien.github.io/zj/zj_e465_1.html)，使用 bitset 求指定資料可能的總合主要參考 LeetCode 416. Partition Equal Subset Sum 討論區 [C++ Bitset Solution](https://leetcode.com/problems/partition-equal-subset-sum/solutions/950597/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進位值為
```python
0b11
```
這代表 possSum 可能為 1。接下來再向左平移7位並與原本的值取 or 運算，其2進位值為
```python
0b110000011
```
這代表 possSum 可能為 1、7、8，也就是看2進位值中哪幾個位數是1，就代表總合可能是這幾個位數。接下再代入 2、8、2 的結果依序為
```python
0b11110001111
0b1111000111110001111
0b111111011111110111111
```
再由最後一位向前搜尋字串1，如果 target 對應的位數不是1，再繼續向前找，找到的位數就是答案。
<br />
於 ZeroJudge 測試結果，最長運算時間約為 46 ms，使用記憶體最多約為 3.5 MB，通過測試。
```python=
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))
```
<br />
### 寫法2，使用二維陣列及 DP
於 ZeroJudge 測試結果，有6筆測資需要的記憶體爆掉。
```python=
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)
```
<br />
### 寫法3，使用滾動陣列及 DP
於 ZeroJudge 測試結果，最後一筆測資超時。
```python=
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)
```
<br /><br />
## C++ 程式碼
### 寫法1，使用 bitset
於 ZeroJudge 測試結果，最長運算時間約為 7 ms，使用記憶體最多約為 704 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
int solve(vector<int> array, int tar);
int main() {
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 << endl;
else
cout << solve(data, target) << endl;
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;
}
```
<br />
### 寫法2，使用二維陣列及 DP
於 ZeroJudge 測試結果，最長運算時間約為 39 ms，使用記憶體最多約為 39.4 MB，通過測試。
```cpp=
#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;
}
```
<br />
### 寫法3，使用滾動陣列及 DP
於 ZeroJudge 測試結果，最長運算時間約為 17 ms，使用記憶體最多約為 1.1 MB，通過測試。
```cpp=
#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;
}
```
<br /><br />
---
###### tags:`APCS`、`Python`、`C++`
Sign in with Wallet
Connect another wallet