1 条题解
-
0
[E] Knapsack 2(dp_e)题解
题意简述
同 Knapsack 1,但 ,而 、。
思路
换个维度做 DP
按重量做 DP 需要 空间与时间, 高达 不可行。但总价值 ,很小。
于是交换"维度的角色":设
- = 达到总价值恰好为 时所需的最小总重量。
转移(对每件 ,同样倒序枚举价值):
最后答案是
为什么正确
精确刻画了"价值达到 的最小代价(重量)"。若某个 能以不超过 的重量达成,那么它就是可行答案;在所有可行的 中取最大。
复杂度
时间 ,空间 。
参考代码
#include <cstdio> #include <algorithm> using namespace std; long long g[100005]; // g[v] = 达到价值 v 的最小重量 int main() { int n, W; scanf("%d %d", &n, &W); const long long INF = (1LL << 60); for (int v = 0; v <= 100000; v++) g[v] = INF; g[0] = 0; int V = 0; for (int i = 0; i < n; i++) { long long w; int v; scanf("%lld %d", &w, &v); for (int j = V + v; j >= v; j--) if (g[j - v] + w < g[j]) g[j] = g[j - v] + w; V += v; } int ans = 0; for (int v = 0; v <= V; v++) if (g[v] <= W) ans = v; printf("%d\n", ans); return 0; }易错点
- 是"恰好等于 "的语义,初值必须是 INF,;否则"不超过"的语义会让答案偏大。
- 求答案要枚举所有 找满足 的最大者,不能只看 。
- 重量相加上限 会超 int,
w与 都用long long。
数据说明
共 14 组:3 组官方样例;、单物品 、全部 、全部 边界; 随机(含 接近 、 集中在 900–1000 的构造);专门放了"全部 而 "的组,检验只看最小重量的实现是否正确。
- 1
信息
- ID
- 14
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者