01背包问题和house robber
来源：9-5 0-1背包问题
软件工程小白菜
2019-07-03
波波老师您好，我对这两个问题的理解是，他们都是要从n个物品中找到一个排列，使得这个排列的总价值最大，只不过这两个问题的约束条件不同，01背包问题的约束条件为总重量的限制，而house robber的约束条件为排列中不能有相邻的两个数。
那么我的问题是为什么我们不能用思考house robber转移方程的方式来思考01背包的转移方程？比如说我们要考虑把[0...n-1]个物品放入容量为C的背包，那么我们可以
把第0个物品放入背包，然后考虑把[1...n-1]个物品（总共有n-1个物品）放入容量为C-w(0)的背包中
不把第0个物品放入背包，但把第1个物品放入背包，然后考虑把[2...n-1]个物品（总共有n-2个物品）放入容量为C-w(1)的背包中
不把第0和第1个物品放入背包，但把第2个物品放入背包，然后考虑把[3...n-1]个物品（总共有n-3个物品）放入容量为C-w(2)的背包中
...
所以以此类推，根据上述过程，是否可以把状态转移方程写为：F(n, C) = max ( v(0)+F( n-1,C-w(0) ) , v(1)+F( n-2,C-w(1) ) , v(2)+F( n-3, C-w(2) ) ....v(i)+F( n- (i + 1) , C-w(i) ) ,..., v(n-1), 0) ？
请问老师这样写出来的状态转移方程，是否本质上和课程中描述的一次考虑一件物品的转移方程相同呢？
谢谢老师！
1回答
-
可以的：）
但是，你的这个转移方程，比我们在课程中介绍的转移方程复杂很多：）
你的这个状态转移方程转移的过程相当于是O(n)的，而课程中介绍的方法，转移过程是O(1)的（因为不管i是多少，只向两个状态转移。）
赞思考！：）
继续加油！：）
232019-07-03
相似问题