完全背包问题

【问题描述】有 n 种物品和一个容量为 C 的背包。第 i 种物品的重量是 w[i]，价值是 v[i]，数量无限。求解将哪些物品装入背包可使价值总和最大。

(1) 基本算法

1. 状态转移方程：f[i][c]＝max{f[i－1][c－k×w[i]]＋k×v[i]}，0≤k×w[i]≤c

å

C

时间复杂度O(C×)，比较大。

w[i]

2. 一个简单的优化：如果物品 i、j 满足 w[i]≤w[j]且 v[i]≥v[j]，就可以把物品 j 去掉。

不过它不能改善最坏情况的复杂度（最坏情况：根本没有可以去掉的东西）。

3. 另一种优化：首先将重量大于C的物品去掉，然后使用类似桶排序或计数排序的方法，计算出费用相同的物品中哪个价值最高。

(2) 更优的算法

// 内层的for和外层的for可以互换。

for (int i=1;i<=n;i++)

for (int c=0;c<=C;c++)     // 这里发生了变化——循环次序变了   if (c>=w) f[c] = max(f[c], f[c-w] + v);

时间复杂度：O(NC)

ìf[i－1][c]

转化为二维，状态转移方程就是：f[i][c]＝maxíîf[i][c－w[i]]＋v[i] （第二行变了）