摘要: 背包如此之妙(有依賴的背包)
題目大意:給你一系列物品清單,其中兩物品直接可能存在主附關系,即要買附件必須將其附件也買下,比如若桌子跟椅子是主附關系,那么想買椅子則必須桌子也買下……問題來了,給你錢N,物品若干,快快買吧……如何買?
dp[j]表示錢為j的時候買得東西的最大價值
一、當物品為主件時:
1、沒有附件
MAX(不買,買主件)
2、有一個附件
MAX(不買,只買主件,買主件與一附件)
3、有兩個附件
MAX(不買,只買主件,買主件與一附件,買主件與兩附件)
二、當物品為附件時:直接跳過
閱讀全文