每日c/c++题 备战蓝桥杯(P1049 [NOIP 2001 普及组] 装箱问题)

洛谷P1049 装箱问题题解：动态规划在背包问题中的经典应用

题目描述

P1049 装箱问题是一道典型的0-1背包问题变种。题目要求在给定箱子容量V和n个物品体积的情况下，选择若干物品装入箱子，使得箱子的剩余空间最小。最终输出这个最小剩余空间的值。

解题思路

本题本质是求不超过箱子容量的最大装载体积，属于经典的0-1背包问题。动态规划是解决此类问题的最优解法，其核心思想是通过状态转移方程逐步构建最优解。

动态规划三要素

代码详解

#include<bits/stdc++.h>
using namespace std;

int main() {
int v, n;
int w[35] = {0}; // 存储物品体积（1-based索引）
int dp[20005] = {0}; // 动态规划数组

cin >> v >> n;
for(int i = 0; i < n; ++i) {
cin >> w[i];
}

for(int i = 0; i < n; ++i) { // 遍历每个物品
for(int j = v; j >= w[i]; —j) { // 逆序遍历背包容量
dp[j] = max(dp[j], dp[j – w[i]] + w[i]);
}
}

cout << v – dp[v]; // 剩余空间=总容量-最大装载体积
return 0;
}

关键代码解析

复杂度分析

• 时间复杂度：O(nV)，其中n为物品数量，V为背包容量
• 空间复杂度：O(V)，使用一维数组优化空间
• 实际表现：当n=30，V=20000时，总运算量约为60万次，可在1秒内完成

注意事项

样例分析

输入：

24
6
8
3
12
7
9
7

执行流程：

输出：

0

优化方向

总结

本题通过动态规划巧妙地将组合优化问题转化为状态转移问题。核心在于理解：

• 0-1背包问题的状态转移特性
• 逆序遍历的必要性
• 结果计算的特殊处理方式

该解法在洛谷测试点中表现优异，能够正确处理包括完全装满、部分装载、无法装载等所有边界情况，是解决此类背包问题的标准范式。