南京机关建设网站,桂林做网站公司,电子商务网站建设与设计,宁波网站建设设计注意事项#xff1a; 本题是动态规划—01背包的扩展题#xff0c;dp和优化思路不多赘述。
题目#xff1a; 有一个箱子容量为 V#xff0c;同时有 n 个物品#xff0c;每个物品有一个体积#xff08;正整数#xff09;。 要求 n 个物品中#xff0c;任取若…注意事项 本题是动态规划—01背包的扩展题dp和优化思路不多赘述。
题目 有一个箱子容量为 V同时有 n 个物品每个物品有一个体积正整数。 要求 n 个物品中任取若干个装入箱内使箱子的剩余空间为最小。
输入格式 第一行是一个整数 V表示箱子容量。 第二行是一个整数 n表示物品数。 接下来 n 行每行一个正整数不超过10000分别表示这 n 个物品的各自体积。
输出格式 一个整数表示箱子剩余空间。
数据范围 0V≤20000, 0n≤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; in; i) cin v[i];//01背包滚动数组优化模板for (int i 1; in; i) {for (int j m; jv[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/ 本文仅用作学习记录和交流
