物品分组(01)背包问题
该问题是在(01)背包问题上附加条件“所有物品一开始被划入了几个不相交的物品组，且每组只能从中取其中一个”。这里不妨规定物品组也以序列给出，而每个物品组又都是1个物品序列。这里稍微改下\(F(k,V)\)的定义为“体积\(V\)的背包与物品组前\(k+1\)项子序列能取到的最大总价值”，即\(k\)是关于物品组的。
列出状态转移方程\(F(k,V) =max\{~F(k-1,V),~max\{ F(k-1, V-A_{k,i}) + B_{k,i} | i\in [0,|A_k|-1] \}~ \} \)，\(i\)是当前物品分组中的物品下标，\(A,B\)按二维数组(物品分组下标，物品下标)提供。得到方程的思路跟其他背包问题相似，这里略去讨论。要注意边界情况的处理，\(V-A_{k,i}<0\)时应直接剔除，不参与求\(max\)。这里同样略去通过\(F\)得到具体解的步骤。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | def dp(A, B, V): f = [[0 for j in range(V + 1)] for i in A] for i in range(len(A)): for j in range(V + 1): subIndexs = [] for k in range(len(A[i])): if j - A[i][k] >= 0: subIndexs.append(k) if i == 0: if len(subIndexs) == 0: f[i][j] = 0 else: f[i][j] = max([ B[i][k] for k in subIndexs]) else: if len(subIndexs) == 0: f[i][j] = f[i - 1][j] else: f[i][j] = max([ f[i - 1][j], max([ f[i - 1][j - A[i][k]] + B[i][k] for k in subIndexs]) ]) return f |