题解 | JS---#购物单#

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 递归方向：
先遍历物品，再遍历背包，遍历背包要从后向前推，防止重复计算