01背包题
[NOIP2006]金明的预算方案
https://ac.nowcoder.com/acm/contest/24213/1024
解题思路：对于某些附件，他们依赖与主件，所以对于某个主件来说，把它的所有附件先找出来，之后最外层for循环直接枚举每一个主件，对于主件的附件在利用一个01背包进行解题。
所以状态定义为：dp[i][j][k] 表示在前n个主件中，j为0表示不选该主件，钱数为k时的最优解，j为1表示选该主件的情况下，钱数为k时的最优解。
状态转移方程为：dp[i][0][k] = max(dp[i-1][0][k], dp[i-1][1][k]);
dp[i][1][k] = 再利用一个01背包求解。
查看10道真题和解析
联想公司福利 636人发布