問題有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。算法這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說設(shè)f[k][v]表示前k組物品花費費用v能取得的最大權(quán)值，則有：f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i屬于組k}使用一維數(shù)組的偽代碼如下：for 所有的組k for v=V..0 for 所有的i屬于組k f[v]=max{f[v],f[v-c[i]]+w[i]}注意這里的三層循環(huán)的順序?！癴or v=V..0”這一層循環(huán)必須在“for 所有的i屬于組k”之外。這樣才能保證每一組內(nèi)的物品最多只有一個會被添加到背包中。另外，顯然可以對每組內(nèi)的物品應(yīng)用P02中“一個簡單有效的優(yōu)化”。小結(jié)分組的背包問題將彼此互斥的若干物品稱為一個組，這建立了一個很好的模型。不少背包問題的變形都可以轉(zhuǎn)化為分組的背包問題（例如P07），由分組的背包問題進一步可定義“泛化物品”的概念，十分有利于解題。
