1 条题解
-
0
[D] Knapsack 1(dp_d)题解
题意简述
件物品,第 件重量 、价值 ,背包容量 ,每件最多取一次,求价值之和最大值。
思路
状态
= 当前已考虑的物品中,总重量恰好不超过 时能获得的最大价值。
转移
对每件物品 ,倒序枚举 从 到 :
倒序是关键:正序会让同一件物品被拿多次(那是完全背包)。倒序保证了
f[j-w]还是"没考虑这件物品"的旧值。为什么正确
这是 0/1 背包的标准做法:按物品顺序决策, 始终表示"前 件物品、容量 的最优值",倒序遍历使得每件物品只被决策一次。
复杂度
时间 ,空间 。
参考代码
#include <cstdio> #include <algorithm> using namespace std; long long f[100005]; int main() { int n, W; scanf("%d %d", &n, &W); for (int i = 0; i < n; i++) { long long w, v; scanf("%lld %lld", &w, &v); for (int j = W; j >= w; j--) f[j] = max(f[j], f[j - (int)w] + v); } printf("%lld\n", f[W]); return 0; }易错点
- 必须倒序循环;正序会变成"物品可重复取"。
- 价值之和最大为 ,远超 int,样例 2 的答案就是 ,必须
long long。 - 初值全 即可(表示什么都不取)。
数据说明
共 16 组:3 组官方样例(含答案 的 64 位用例);、、全 、全 等边界; 随机;两组"全部 "与"全部 "的构造组,专门检验倒序与容量边界。
- 1
信息
- ID
- 13
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者