对0-1背包问题递推方程的理解?

来源：9-5 0-1背包问题

triump

2018-10-19

准确的讲，背包问题的递推方程应该分如下两种情况讨论：
<1> F（i, C）= max{F(i -1, C), F(i - 1, C - w(i)) + v(i)} (当C - w(i) >= 0 ) 或者
<2> F(i, C) = F(i -1, C)(当C - w(i) <0)
如果F(i ,C) 表示恰好把前i 种物品放到C 所获取的最大价值，那就变成了递推方程<1>, 就不用考虑<2>了。

对第<1>个递推方程的准确解释应该是：首先，F(i, C) 表示的意义应该是前 i 种物品放到剩余容量为C 所获取的最大价值（注：并不是说前i种物品都放进去了，具体是哪几种组合，我们并不知晓）
然后，我们假设已经递归处理了前i -1 种物品，并获取了最大价值；那么对于第i 物品此时有两种选择：要么放，
要么不放（不放并不是指此时容量已经剩余的不多了，而只是一种选择而已），这两种情况都有可能达到最优解，所以我们需要比较，取最大值从而保证 F(i ,C)等于最大价值

老师，不知道我的理解对不对？背包问题感觉还是有点不好理解

写回答

2回答