簡化的問題
這種背包問題的物品間存在某種“依賴”的關系。也就是說拨扶，i依賴于j，表示若選物品i茁肠，則必須選物品j患民。為了簡化起見，我們先設沒有某個物品既依賴于別的物品垦梆，又被別的物品所依賴匹颤；另外，沒有某件物品同時依賴多件物品托猩。
算法
這個問題由NOIP2006金明的預算方案一題擴展而來印蓖。遵從該題的提法，將不依賴于別的物品的物品稱為“主件”京腥，依賴于某主件的物品稱為“附件”赦肃。由這個問題的簡化條件可知所有的物品由若干主件和依賴于每個主件的一個附件集合組成。
<p>按照背包問題的一般思路公浪，僅考慮一個主件和它的附件集合他宛。可是欠气，可用的策略非常多厅各，包括：一個也不選，僅選擇主件预柒，選擇主件后再選擇一個附件队塘，選擇主件后再選擇兩個附件……無法用狀態(tài)轉(zhuǎn)移方程來表示如此多的策略袁梗。（事實上，設有n個附件憔古，則策略有2^n+1個遮怜，為指數(shù)級。）
<p>考慮到所有這些策略都是互斥的（也就是說投放，你只能選擇一種策略），所以一個主件和它的附件集合實際上對應于P06中的一個物品組适贸，每個選擇了主件又選擇了若干個附件的策略對應于這個物品組中的一個物品灸芳，其費用和價值都是這個策略中的物品的值的和。但僅僅是這一步轉(zhuǎn)化并不能給出一個好的算法拜姿，因為物品組中的物品還是像原問題的策略一樣多烙样。
<p>再考慮P06中的一句話： 可以對每組中的物品應用P02中“一個簡單有效的優(yōu)化”。 這提示我們蕊肥，對于一個物品組中的物品谒获，所有費用相同的物品只留一個價值最大的，不影響結(jié)果壁却。所以批狱，我們可以對主件i的“附件集合”先進行一次01背包，得到費用依次為0..V-c[i]所有這些值時相應的最大價值f'[0..V-c[i]]展东。那么這個主件及它的附件集合相當于V-c[i]+1個物品的物品組赔硫，其中費用為c[i]+k的物品的價值為f'[k]+w[i]。也就是說原來指數(shù)級的策略中有很多策略都是冗余的盐肃，通過一次01背包后爪膊，將主件i轉(zhuǎn)化為V-c[i]+1個物品的物品組，就可以直接應用P06的算法解決問題了砸王。
較一般的問題
更一般的問題是：依賴關系以圖論中“森林”的形式給出（森林即多叉樹的集合）推盛，也就是說，主件的附件仍然可以具有自己的附件集合谦铃，限制只是每個物品最多只依賴于一個物品（只有一個主件）且不出現(xiàn)循環(huán)依賴耘成。
<p>解決這個問題仍然可以用將每個主件及其附件集合轉(zhuǎn)化為物品組的方式。唯一不同的是驹闰，由于附件可能還有附件凿跳，就不能將每個附件都看作一個一般的01背包中的物品了。若這個附件也有附件集合疮方，則它必定要被先轉(zhuǎn)化為物品組控嗜，然后用分組的背包問題解出主件及其附件集合所對應的附件組中各個費用的附件所對應的價值。
<p>事實上骡显，這是一種樹形DP疆栏，其特點是：每個父節(jié)點都需要對它的各個兒子的屬性進行一次DP以求得自己的相關屬性曾掂。這已經(jīng)觸及到了“泛化物品”的思想”诙ィ看完P08后珠洗，你會發(fā)現(xiàn)這個“依賴關系樹”每一個子樹都等價于一件泛化物品，求某節(jié)點為根的子樹對應的泛化物品相當于求其所有兒子的對應的泛化物品之和若专。
小結(jié)
NOIP2006的那道背包問題我做得很失敗许蓖，寫了上百行的代碼，卻一分未得调衰。后來我通過思考發(fā)現(xiàn)通過引入“物品組”和“依賴”的概念可以加深對這題的理解膊爪，還可以解決它的推廣問題。用物品組的思想考慮那題中極其特殊的依賴關系：物品不能既作主件又作附件嚎莉，每個主件最多有兩個附件米酬，可以發(fā)現(xiàn)一個主件和它的兩個附件等價于一個由四個物品組成的物品組，這便揭示了問題的某種本質(zhì)趋箩。
我想說：失敗不是什么丟人的事情赃额，從失敗中全無收獲才是。
