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

> 日期：2023年9月9日
> 作者：王一哲
> 題目來源：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 程式碼

以下的程式碼主要參考[這個網頁](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進位值為

0b11

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

0b110000011

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

0b11110001111
0b1111000111110001111
0b111111011111110111111

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

於 ZeroJudge 測試結果，最長運算時間約為 46 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))

<br /><br />

## C++ 程式碼

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

#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 /><br />

---

###### tags:`APCS`、`Python`、`C++`