装箱问题（01背包）
文章目录
题目链接：NOIP2001装箱问题
一、原题复现
题目描述
有一个箱子容量为V（正整数，0 ≤ V ≤ 20000），同时有n个物品（0＜n ≤ 30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入描述:
- 1个整数，表示箱子容量
- 1个整数，表示有n个物品
- 接下来n行，分别表示这n个物品的各自体积
输出描述:
1个整数，表示箱子剩余空间。
输入
24
6
8
3
12
7
9
7
输出
0
二、思路剖析
-
首先观察题中希望得到剩余空间最小时剩余的空间值，要达到该要求，需要我们塞入体积总和尽可能多的物体。由于每个物体的体积都是正数，不妨我们将最终推测的目标转换为从众多物品中选取，在总体积不超过V的情况下，使得箱子内的物品总体积尽可能大。最终返回的结果即：“V - 最大总体积”。
-
对于每个物品，他们都有各自对应的体积大小，同时对于达成最终目标而言，都有选择与不被选择两种情况，这两种情况可以分别表示为 ‘0’, ‘1’ ，所以该题应该将 01 背包问题纳入考虑范围。
-
因为有总体积不超过V的限制，所以我们dp数组递推的过程有一个字段是**“峰值容量”**，它的递推范围为 [0, V]。当然，峰值容量为0时，不能装任何物品，那么该字段为0对应的dp表空位可以直接初始化为0。
-
同样地，因为有n个物品，对他们进行标号，也就有了另外一个字段为**“物品序号”**，递推范围为 [1, n]，直接表示为第i个物品。
-
通过上面 (3)、(4) 的分析，最终的 dp 表在两字段对应都需要多开一个位置，便于初始化完成后，对剩余位置的循环递推赋值。不妨设定 i 为前 i 件物品（理由：由于判断第 i 物品时，峰值容量是否足够容纳该物品，而判断总体积时前面的物品也已经装在箱子中），j 为箱子内可容纳的峰值容量。则 dp[i] [j] 表示前 i 件物品，在总体积不超过 j 的情况下，箱子内的最大体积。
-
截止目前我们已经确定了dp表，以及 dp[i] [j] 的含义和 i ,j 的递推范围。那怎么通过其他表格内的信息推出 dp[i] [j] 的值呢？假定存储物品的数组声明为"vec"，我们知道对于第 i 个物品存在 选、不选 两种情况：
- 不选：那么前 i 位置相对于前 i - 1 位置，vec[i]的值就没有叠加，故 dp[i] [j] = dp[i - 1] [j]；
- 选：对于选而言，有个重要的前提，即为当前峰值容量(j) 减去当前物品的体积(vec[i]) 是否大于0。如果大于等于0，说明如果箱内为空可以容纳下该物体，那么此时的最大体积为前 i - 1 个物体，箱子峰值容量为 j - vec[i] 处对应的值加上 vec[i]，即 dp[i - 1] [j - vec[i]] + vec[i]。另外一种递推渠道 dp[i - 1] [j]，最终 dp[i] [j] 位置的值取两者的最大值即可；如果小于0，递推来源就只能是 dp[i - 1] [j]，即 dp[i] [j] = dp[i - 1] [j]。
- 填表顺序也通过上面分析变得很清晰了，最终状态是什么呢? 回到开始，我们将问题转换为利用dp表求在总体积不超过V的情况下，使得箱子内的物品总体积尽可能大。所以，最终状态对应的值为 dp[n] [v]，注意我们循环递推填表下标从 1 开始。最后得到的结果即 v - dp[n] [v]。
三、示例代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int v = 0, n = 0;
cin >> v >> n;
vector<int> vec(n + 1, 0);
for(int i = 1; i <= n; i++)
{
cin >> vec[i];
}
// dp[i][j]: 表示前i个物品，容量不超过j的情况下，箱子的峰值容量
vector<vector<int>> dp(n + 1, vector<int>(v + 1));
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= v; j++)
{
dp[i][j] = (j < vec[i])?
(dp[i - 1][j]):
(max(dp[i - 1][j],
dp[i - 1][j - vec[i]] + vec[i]));
}
}
auto result = v - dp[n][v];
cout << result << endl;
return 0;
}
