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