题解 | JS---#购物单#
购物单
http://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
0/1 背包问题的变种
// 解题思路：
1 初始化dp数组 dp[j] 表示 j 元所购物品的价值最大
2 确定状态转移：
这道背包问题，有三种状态转移选择：
1 选与不选主件 dp[j] = max(dp[j - Money主] + 价值主, dp[j])
2 选与不选附件1 dp[j] = max(dp[j - 附件1] + 价值附件1, dp[j])
3 选与不选附件2，选2就一定要选1 dp[j] = max(dp[j - 附件1 - 附件2] + 价值附件1 + 2, dp[j])
3 初始化：
由于是求最大，所以初始化为0
4 递归方向：
先遍历物品，再遍历背包，遍历背包要从后向前推，防止重复计算
韶音科技公司氛围 296人发布
腾讯三面379人在聊
查看6道真题和解析