数据结构设计: 我使用了 goods[i][3] 这样的二维结构。 goods[i][0] 存放第 i 号物品的主件信息。 goods[i][1] 存放第 i 号主件的第一个附件。 goods[i][2] 存放第 i 号主件的第二个附件。 这样在遍历 i 时,只要判断 goods[i][0] 是否存在,就能一次性拿出这一组的所有搭配。 空间优化: 题目中 v 都是 10 的倍数。代码中 vReal := v / 10,对应的背包总容量 n /= 10。这能让 DP 数组的大小缩小 10 倍,速度和空间都更优。 互斥决策: 在内层 j 的循环中,我们针对同一个主件组尝试了 4 种方案。因为是在同一个 j 的循环里取 max,这保证了对于当前的钱 j,我们只会选择这 4 种方案里的某一种(或者不买),而不会出现“买了一个主件又买了同一个主件”的错误。
点赞

相关推荐

01-12 17:45
门头沟学院 Java
985废物一枚:就是问问你能不能接受北京的房租,hr也知道公司工资不高,大概率是要贴钱的
找实习记录
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务