【问题描述】有 n 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i],价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。 (1) 二维数组表示 1. 定义状态:f[i][c]表示前 i 件物品恰放入一个容量为 c 的背包可以获得的最大价值。 2. 状态转移方程:f[i][c]=maxíîìff[[ii--1][1][cc-] w[i]]+v[i] ((不选这件物品选择这件物品)) // 注意边界处理 for (int i=1;i<=n;i++) for (int c=0;c<=C;c++) { f[c]=f[i-1][c]; if (c>=w) f[c] = max(f[c], f[i-1][c-w] + v); } |
时间复杂度、空间复杂度:都是O(NC) (2) 一维数组表示 1. 定义状态:由于递推的过程和雪天环形路上的扫雪车类似,所以可以把 i 省略。 ìf[c] (不选这件物品)2. 状态转移方程:f[c]=maxíîf[c-w[i]]+v[i] (选择这件物品) 递推时注意 c 要从 C 开始,倒着推。 // 注意边界处理 for (int i=1;i<=n;i++) for (int c=C;c>=0;c--) if (c>=w) f[c] = max(f[c], f[c-w] + v); 时间复杂度:O(NC) 空间复杂度:降到了O(C) (3) 一维之下的一个常数优化 其实没有必要让循环下限为0。 int bound, sumw=0; for (int i=1;i<=n;i++) { sumw+=w; bound = max(C – sumw, w); |
for (int c=C;c>=bound;c--) if (c>=w) f[c] = max(f[c], f[c-w] + v); } (4) 初始化时的细节 如果要求“恰好装满”,那么初始化时应该让 f[0]=0,其他的 f=-INF。这样就可以知道是否有解了。 如果不用“恰好”,那么应该让 f 的所有元素都置0。
|