1 条题解
-
0
【本题解由站长编写】
01 背包求最小剩余空间:dp[v] 表示体积 v 是否可达(或一维最大可装体积),答案为 V − 最大可达体积。V≤20000、n≤30。
代码(C++17)
#include <bits/stdc++.h> using namespace std; int main() { int V, n; cin >> V >> n; vector<bool> ok(V + 1, false); ok[0] = true; for (int i = 0; i < n; i++) { int v; cin >> v; for (int j = V; j >= v; j--) if (ok[j - v]) ok[j] = true; } int best = 0; for (int j = V; j >= 0; j--) if (ok[j]) { best = j; break; } cout << V - best << endl; return 0; }
- 1
信息
- ID
- 4311
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者