問題描述
????有N件物品和一個(gè)容量為V的背包什黑。第i件物品的費(fèi)用是c[i]碧库，價(jià)值是w[i]盅粪。這些物品被化為若干組钓葫，每組中的物品相互沖突，最多選一件湾揽。求解將哪些物品裝入背包可以使這些物品的體積總和不超過背包最大容量瓤逼，且價(jià)值總和最大。
思路分析
????這個(gè)問題變成了每組物品有若干選擇策略:是選擇本組中的一件還是一件都不選库物。設(shè)f[k][j]表示考慮前k組物品可獲得的最大價(jià)值霸旗，狀態(tài)轉(zhuǎn)換方程為:
????????????????????????f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]} 物品i屬于組k
偽代碼
//注意這里是三層循環(huán)
for 所有的組k
for v=V to 0
for 所有屬于組k的i
f[v]=max{f[v],f[v-c[i]]+w[i]}
end
end
end
