这道题看似是搜索，但是可以用背包做。 题目要求求出最小的剩余空间，也就是要求出最大的可装重量 这样，我们可以将一个物体的重量当作它的价值，进而将题目转变为一个基本的 010101 背包问题： 有一个箱子容量为 VVV （正整数， 000 ＜＝ VVV ＜＝ 200002000020000 ），同时有 nnn 个物品（ 000 ＜ nnn ＜＝ 303030 ），每个物品有一 个体积（正整数）和一个价值（等于体积）。 要求 nnn 个物品中，任取若干个装入箱内，使总价值最大。 对于每一个物体，都有两种状态：装 与不装 那么，对于任意重量 mmm 的最大价值 fff ( mmm ) === maxmaxmax ( fff ( mmm −-− www [ iii ] ) +++ www [ iii ], fff ( mmm ) )（ www 为重量（即价值）） 其中， fff ( mmm −-− www [ iii ] ) 指在装了物品 iii 后，箱子的剩余容量能装的最大重量 fff ( mmm −-− www [ iii ] ) +++ www [ iii ] 指在在装了物品 iii 后，箱子能装的最大重量

洛谷里这个没有re的

逝十分简单的一道01背包的题 欢迎加入团队

这道题属于子集枚举的典型例题。对于每个物品有两种做法：选与不选，所以需要用递归枚举。递归每一层枚举选和不选的情况，顺带算好当前物品体积之和。如果n个物品枚举完，则将此次剩余空间值与最小剩余值进行对比，反复更新。

题解： 问题分析 这是一个经典的01背包问题变形。我们要从 n 个物品中选择若干件放入容量为 V 的箱子，使得剩余空间最小。 关键转化： * 剩余空间最小 = 装入物品的总体积最大 * 装入物品总体积 ≤ 箱子容量 V * 目标：在不超过容量的前提下，尽可能多装物品 因此，问题转化为： 求在容量 V 限制下，能装入物品的最大总体积 解题思路 方法：动态规划（01背包） 定义 dp[j] 表示容量为 j 的箱子能装的最大物品总体积。 状态转移方程： 倒序枚举是为了确保每个物品最多被选择一次（01背包特点）。 算法步骤： 1. 输入箱子容量 V 和物品数量 n 2. 初始化 dp 数组为 0 3. 对于每个物品，更新 dp 数组 4. 最终答案为 V - dp[V] 时间复杂度：O(N×V) * n ≤ 30, V ≤ 20000，计算量约为 60 万次操作，完全可行 代码实现 样例解释 样例输入： 最优装法：8 + 3 + 7 + 6 = 24（刚好装满） 剩余空间 = 24 - 24 = 0 注意事项 1. 数组大小要开到 20000 以上 2. 内层循环必须倒序，保证每个物品只选一次 3. 初始条件 dp[0] = 0 表示空箱子容量为 0 时装的物品体积为 0 总结 本题是标准的01背包问题，通过动态规划可以高效求解。关键是理解“剩余空间最小”等价于“装入物品总体积最大”。

典型的背包问题，动归问题，原题在ybt

很正常的01背包，动态公式为 dp[j]=dp[j-w[i]]+w[i] 上代码——