背包问题!

【问题描述】有 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。