这一篇文章我们跳过了《背包九讲》中的多重背包、混合背包等章节，直接讲分组背包，这是因为我觉得在学习完01背包和完全背包之后，对这些问题的理解不会太困难。所以我们这一篇文章直接讲分组背包。

题目

有 N 件物品和一个容量为 V 的背包。第i件物品的费用是 Ci ，价值是 Wi 。这些物品被划分为 K 组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

题目分析

对于题目中的每组物品，可以选择该组的某一件，或者一件都不选。所以我们可以得到状态转移方程F[k, v] = max{F[k − 1, v], F[k − 1, v − Ci] + Wi | item i ∈ group k}，其中F[k, v]表示前k组物品花费费用v能取得的最大价值。如果要使用一维数组的话，那么循环将变成三重循环。

实现代码

for k = 1 to K
	for v = V to 0
		for item i in group k
			F[v] = max{F[v], F[v − Ci] + Wi}