背包问题系列之--分组背包问题

问题描述

    有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被化为若干组，每组中的物品相互冲突，最多选一件。求解将哪些物品装入背包可以使这些物品的体积总和不超过背包最大容量，且价值总和最大。

思路分析

    这个问题变成了每组物品有若干选择策略:是选择本组中的一件还是一件都不选。设f[k][j]表示考虑前k组物品可获得的最大价值，状态转换方程为:
                        f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]} 物品i属于组k

伪代码

//注意这里是三层循环
for 所有的组k
  for v=V to 0
    for 所有属于组k的i
      f[v]=max{f[v],f[v-c[i]]+w[i]}
    end
  end
end