把装箱问题化成"体积=价值"的 0/1 背包：逐件物品倒序扫容量做一维 DP，dp[V] 即最大装载体积，答案为 V-dp[V]。
OJ: roj
题目 ID: 3507
难度:普及-
标签:动态规划背包01背包python
创建: 2026-10-02 04:05
更新: 2026-10-06 12:15
题目描述
容量为 V（0<V≤20000）的箱子，有 n（0<n≤30）件体积为正整数的物品，任取若干件装入箱内，使箱子剩余空间最小。
输入第一行 V，第二行 n，之后 n 行每行一件物品体积；输出一个整数，即最小剩余空间。
样例输入 24 / 6 / 8 / 3 / 12 / 7 / 9 / 7，输出 0。
思路
把"体积"同时当作"价值"，问题就是 0/1 背包：最大化装入的总体积，答案即 V 减去该最大值。用一维 dp[c] 表示容量 c 能装下的最大体积，每件物品倒序扫容量做 dp[c]=max(dp[c],dp[c-w]+w)，总时间 O(nV)。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 04:05
# update_at: 2026-10-02 04:05
import sys
def knapsack(cap: int, vols: list[int]) -> list[int]:
"""0/1 背包：dp[c] = 只用已处理物品、容量 c 时能装下的最大总体积。"""
dp = [0] * (cap + 1)
for v in vols:
# 倒序扫容量，保证每件物品只被选一次
dp[v:] = map(max, dp[v:], (used + v for used in dp[:-v or None]))
return dp
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
box_volume = next(data) # 箱子容量 V
n = next(data)
vols = [next(data) for _ in range(n)]
best = knapsack(box_volume, vols)[box_volume]
print(box_volume - best) # 装得越多，剩余空间越小
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 12:15
* update_at: 2026-10-06 12:15
*/
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXV = 20005;
int dp[MAXV]; // dp[c]：只用已处理过的物品、容量 c 时能装下的最大总体积
int main() {
int V; // 箱子容量
int n; // 物品件数
cin >> V >> n;
// 0/1 背包：体积即价值，装入总体积越大，剩余空间越小
for (int i = 1; i <= n; i++) {
int w;
cin >> w;
// 倒序扫容量，保证每件物品最多被装入一次
for (int c = V; c >= w; c--) {
if (dp[c - w] + w > dp[c]) {
dp[c] = dp[c - w] + w;
}
}
}
cout << V - dp[V] << endl; // 最小剩余空间
return 0;
}