題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P1049 [NOIP 2001 普及组] 装箱问题

Problem Statement

題目簡述

給定一個容量為 $V$ 的箱子與 $n$ 個物品，每個物品都有自己的體積且最多只能選一次。
請選擇若干物品放入箱子，在總體積不超過 $V$ 的前提下，讓箱子的剩餘空間最小。

Constraints

約束條件

$1 \le V \le 20000$
$1 \le n \le 30$
每個物品體積皆為正整數

思路：位元集合最佳化 0/1 背包

核心轉換

剩餘空間最小，等價於在不超過容量的前提下，讓放入箱子的總體積最大。

因此只要記錄「哪些總體積可以被湊出」，最後取不超過容量的最大可達體積即可。

核心觀察

只關心某個總體積能不能湊出，不需要記錄具體選了哪些物品。

位元集合表示狀態

一般 0/1 背包可用布林陣列表示可達體積，但我們也可以把一個大整數或bitset當作布林陣列的壓縮表示：第 $i$ 位為 $1$ 代表總體積 $i$ 可達，為 $0$ 代表不可達。

若用一般 0/1 背包表示，令狀態代表「體積 $j$ 是否可達」，處理一件體積為 $x$ 的物品時，轉移為：

dp_j \leftarrow dp_j \lor dp_{j - x}

意思是：體積 $j$ 原本可達，或是原本能湊出 $j - x$ ，再放入這件物品後變成 $j$ 。

觀察這個轉移，所有「由 $j - x$ 轉移到 $j$ 」其實就是把整個可達狀態往右邊平移 $x$ 格。若把布林陣列壓成 bitset，第 $i$ 位代表體積 $i$ 是否可達，那麼這個平移就可以直接用左移完成：

state \leftarrow state \lor (state \ll x)

其中原本的 state 表示「不選這件物品」，state << x 表示「選這件物品」後新增的可達體積。兩者合併後，就得到處理完這件物品後的所有可達體積。

左移後可能出現超過容量的狀態，這些不可能成為答案，所以用遮罩只保留 $0$ 到 $V$ 的 bit。

取出答案

所有物品處理完後，最高的可達體積就是能塞入的最大總體積，因此答案為：

V - \text{最大可達體積}

在 Python 中可以用 bit_length() 找出最高可達位。

複雜度分析

時間複雜度： $\mathcal{O}(n \cdot \dfrac{V}{w})$ ，其中 $w$ 為機器字長，通常為 $32$ 或 $64$ 。
空間複雜度： $\mathcal{O}(\dfrac{V}{w})$

Code

def solve():
    V = int(input())
    n = int(input())
    A = [int(input()) for _ in range(n)]

    f = 1
    U = (1 << (V + 1)) - 1
    for x in A:
        f |= f << x
        f &= U
    print(V - (f.bit_length() - 1))


if __name__ == "__main__":
    solve()