P1049 装箱问题
对应章节：五、数据结构与算法 → （十二） 搜索：递归、回溯、DFS、BFS 与记忆化；五、数据结构与算法 → （十三） 动态规划（DP）基础。
（一） 任务与输出目标
每件至多取一次，使装入体积最大，输出剩余容量。
（二） 建模与推导
定义 f(i,j) 为只使用前 i 种（件）物品、总消耗不超过 j 的最大价值。按是否使用第 i 种分类：不用时来自 f(i-1,j)；使用时删去一份，剩余容量是 j-cost，接回得到前驱价值加 value。
每件只用一次，删掉当前件后剩余物品范围必须是前 i-1 件，所以前驱为 f(i-1,j-cost)。由此 \(f(i,j)=\max(f(i-1,j),f(i-1,j-cost)+value)\)。压成一维后容量倒序，j-cost 还没有在本轮更新，读到的是上一件处理结束的状态。
初始全为 0，表示不取物品；较优前驱替换较差前驱后，物品范围与总消耗仍成立，所以只保存最大价值。所有物品处理后读总容量位置。装箱时把体积同时当作价值，输出容量减去最大装入体积。
（三） 手算与过程
容量 5，体积 2、4：最好装入 4，剩余 1。
（四） 带注释实现
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve() {
int capacity, n;
cin >> capacity >> n;
vector<int> dp(capacity + 1, 0);
for (int i = 0; i < n; ++i) {
int cost, value;
cin >> cost;
value = cost; // 体积本身就是希望装入的价值。
for (int j = capacity; j >= cost; --j)
dp[j] = max(dp[j], dp[j - cost] + value); // 倒序读取上一轮状态，每件只用一次。
}
cout << capacity - dp[capacity] << '\n';
}
signed main() {
ios::sync_with_stdio(false); // 关闭同步，使用 cin 与 cout 完成输入输出。
cin.tie(0), cout.tie(0);
int T = 1; // 本题读入一组数据。
// cin >> T; // 题目给出测试组数时开启，并在 solve 中处理一组。
while (T--)
solve();
}（五） 复杂度
时间 \(O(nC)\)，一维空间 \(O(C)\)。