C++---背包模型---装箱问题（每日一道算法2023.3.9）

注意事项：
本题是"动态规划—01背包"的扩展题，dp和优化思路不多赘述。

题目：
有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。
要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入格式
第一行是一个整数 V，表示箱子容量。
第二行是一个整数 n，表示物品数。
接下来 n 行，每行一个正整数（不超过10000），分别表示这 n 个物品的各自体积。

输出格式
一个整数，表示箱子剩余空间。

数据范围
0<V≤20000,
0<n≤30

输入:
24
6
8
3
12
7
9
7

输出：
0

#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 20010;
int n, m;
int v[N], f[N];

int main () {
    cin >> m >> n;
    for (int i = 1; i<=n; i++) cin >> v[i];
    
    //01背包，滚动数组优化模板
    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]); //直接将v[i]本身当作价值，替换掉w[i]
        }
    }

    cout << m-f[m];  //求的是总体积减去最大体积，即为剩余体积
    return 0;
}

思路：
v[i]保持原位时看作 物品体积，在替换掉w[i]时看作 物品价值。
其实就是将01背包中的 ”物品价值“ 等价替换为 “物品体积”，其余部分不变即可。

声明：
算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流