分组背包问题

---

拥有相互排斥的物品（爆炸物）怎么办？

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

for 所有的组k 
for 所有的i属于组k 
for v=V1..Vk 
f[v]=max{f[v],f[v-c[i]]+w[i]}