【题目来源】
洛谷：P1049 [NOIP 2001 普及组] 装箱问题 - 洛谷 (luogu.com.cn)
【题目描述】
有一个箱子容量为 \(V\)，同时有 \(n\) 个物品，每个物品有一个体积（正整数）。
要求 \(n\) 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间为最小。输出这个最小值。
【输入】
第一行是一个整数 \(V\)，表示箱子容量。
第二行是一个整数 \(n\)，表示物品数。
接下来 \(n\) 行，每行一个正整数，表示第 \(i\) 个物品的体积。
【输出】
共一行一个整数，表示箱子最小剩余空间。
【输入样例】
24
6
8
3
12
7
9
7
【输出样例】
0
【算法标签】
《洛谷 P1049 装箱问题》 #动态规划DP# #递归# #背包DP# #NOIP普及组# #2001#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 20005; // 定义常量 N，表示最大容量
int n, m; // n 表示物品的数量，m 表示背包的容量
int f[N]; // f 数组用于存储背包容量为 j 时的最大价值int main()
{cin >> m >> n; // 输入背包容量 m 和物品数量 nfor (int i = 1; i <= n; i++) // 遍历每个物品{int v;cin >> v; // 输入当前物品的体积 v（同时也是价值）// 动态规划更新 f 数组for (int j = m; j >= v; j--) // 从大到小遍历背包容量{f[j] = max(f[j], f[j - v] + v); // 更新 f[j]，选择是否放入当前物品}}cout << m - f[m] << endl; // 输出剩余容量（总容量减去最大装入体积）return 0;
}
【运行结果】
24
6
8
3
12
7
9
7
0