最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

题目给定一个容量为 $m$ 的箱子，以及 $n$ 个物品

每个物品 $i$ 有一个体积 $v_i$

要求我们找出一个装箱方案，使得箱子的剩余空间最小

分析

本题也是一个 01背包 的题目

可以很直接的通过题目的字眼分析出来 01背包模型

一共有 $n$ 个物品，$m$ 的容量，每个物品有一个体积 $v_i$

而题目没有直接给出物品的 价值，但是题目要求我们选择物品的时候，在体积不超过容量的情况下最大

因此我们可以抽象出来物品的 价值$w_i$ 就是物品的 体积$v_i$

然后就是经典的 01背包的DP模型

对于01背包这里我不再额外的阐述，具体可以参见我的这个博客 AcWing 423. 采药【01背包DP模型】

这里面把01背包模型的分析、集合划分、求解以及所有的优化方式都进行了详细的阐述

Code

时间复杂度：$O(nm)$

空间复杂度：$O(m)$

#include <iostream>

using namespace std;

const int N = 35, M = 20010;

int n, m;
int v[N];
int f[M];

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; ++ i) cin >> v[i];
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = m; j >= v[i]; -- j)
        {
            f[j] = max(f[j], f[j - v[i]] + v[i]);
        }
    }
    cout << m - f[m] << endl;
    return 0;
}