题目
题解
1 |
|
其中核心代码:
1 | // TODO Write your code here! |
做这道题时发现对0-1背包问题还是有误解。现在重新捋一遍思路。
0-1背包本质是动态规划,那么用动态规划的思路,我们如何把背包问题分解为子问题?
我们每次只需要对一件物品做一次决定,而这个决定如何做,取决于哪个决定可以给我们带来最优结果。假设我们现在已经处理到最后一件物品了,假设此时我们的状态为pre
,那么我们需要求做完此次决定之后的最优状态集合curr
:
一定要注意我们所选择的状态的含义:在做选择之前,剩余容量为
c
,curr[c]
代表以此状态为初始状态进行选择,所能获得的最优结果,简单来说,其 key-value 为初始状态-最优结果;在做选择之前,我们处于
pre
的状态集合中,当前物品重量w
,价值p
,对于每一种c
的初始状态,我们需要做选择得到最优结果;如果我们选择了这个物品,那么总价值就要添加
p
,而为了选择这个物品,我们的背包容量首先得足够容纳它,其次,我们剩余的背包容量要发挥最大作用,也就是要剩余背包容量的限制下做到最优,也就是pre[c-w]
,此时总价值curr[c]=pre[c-w]+p
;如果不选,那么背包剩余空间不变,我们要使其发挥最大作用,此时
curr[c]=pre[c]
;
以上是递归思路,而我们实现时一般使用迭代,相当于将物品依次添加到集合中。
将递归实现的思路理解为这样一种过程:现在来了一件新物品,我选还是不选?我现在已经知道不同的背包容量情况下,在不计算这件物品时我能取得的最大价值,我只需要比较两种选择的结果选最优即可。