Merlin's Blog

##**问题** 有$N$件物品和一个容量为$V$的背包。第$i$件物品的费用是$C_i$，价值是$W_i$。这 些物品被划分为$K$组，每组中的物品互相冲突，最多选一件。求解将哪些物品 装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 ##**算法** 这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设$F[k,v]$表示前$k$组物品花费费用