天津最新的疫情消息北方网/外贸网站建设优化推广

注意事项：
本题是"动态规划—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/
本文仅用作学习记录和交流