【正经题解】装箱问题

题解：

问题分析

这是一个经典的01背包问题变形。我们要从 n 个物品中选择若干件放入容量为 V 的箱子，使得剩余空间最小。

关键转化：

• 剩余空间最小 = 装入物品的总体积最大
• 装入物品总体积 ≤ 箱子容量 V
• 目标：在不超过容量的前提下，尽可能多装物品

因此，问题转化为：
求在容量 V 限制下，能装入物品的最大总体积

解题思路

方法：动态规划（01背包）

定义 dp[j] 表示容量为 j 的箱子能装的最大物品总体积。

状态转移方程：

对于每个物品 i（体积为 w）：
    对于 j 从 V 到 w（倒序枚举）：
        dp[j] = max(dp[j], dp[j-w] + w)

倒序枚举是为了确保每个物品最多被选择一次（01背包特点）。

算法步骤：

1. 输入箱子容量 V 和物品数量 n
2. 初始化 dp 数组为 0
3. 对于每个物品，更新 dp 数组
4. 最终答案为 V - dp[V]

时间复杂度：O(n×V)

• n ≤ 30, V ≤ 20000，计算量约为 60 万次操作，完全可行

代码实现

#include<bits/stdc++.h>
using namespace std;
int dp[20005];
int main(){
    int V,n,w;
    cin>>V>>n;
    for(int i=0;i<n;i++){
        cin>>w;
        for(int j=V;j>=w;j--){
            dp[j]=max(dp[j],dp[j-w]+w);
        }
    }
    cout<<V-dp[V];
    return 0;
}

样例解释

样例输入：

24
6
8
3
12
7
9
7

最优装法：8 + 3 + 7 + 6 = 24（刚好装满）
剩余空间 = 24 - 24 = 0

注意事项

1. 数组大小要开到 20000 以上
2. 内层循环必须倒序，保证每个物品只选一次
3. 初始条件 dp[0] = 0 表示空箱子容量为 0 时装的物品体积为 0

总结

本题是标准的01背包问题，通过动态规划可以高效求解。关键是理解“剩余空间最小”等价于“装入物品总体积最大”。