分组的背包问题

【问题描述】有 n 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。这些物品被划分为K组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使价值总和最大。

1. 状态表示：设 f[k][c]为前 k 组物品花费 c 时可以获得的最大价值。

ìf[k－1][c]

2. 状态转移方程：f[k][c]＝maxíîf[k－1][c－w[i]]＋v[i]  物品i属于第k组  注意循环的顺序。

for (int k=1;i<=K;i++)

for (int c=C;c>=0;c--)

  for each (int i in 第k组)  // 伪代码，指“for (所有属于组k的物品i)”    if (c>=w) f[c] = max(f[c], f[c-w] + v);

在“金明的预算方案”（NOIP2006,2）中，就可以把主件、附件组合成一个分组背包（一组最多4个物体，最少1个物体）。