01背包问题和house robber

Question

波波老师您好，我对这两个问题的理解是，他们都是要从n个物品中找到一个排列，使得这个排列的总价值最大，只不过这两个问题的约束条件不同，01背包问题的约束条件为总重量的限制，而house robber的约束条件为排列中不能有相邻的两个数。

那么我的问题是为什么我们不能用思考house robber转移方程的方式来思考01背包的转移方程？比如说我们要考虑把[0...n-1]个物品放入容量为C的背包，那么我们可以

1. 把第0个物品放入背包，然后考虑把[1...n-1]个物品（总共有n-1个物品）放入容量为C-w(0)的背包中

2. 不把第0个物品放入背包，但把第1个物品放入背包，然后考虑把[2...n-1]个物品（总共有n-2个物品）放入容量为C-w(1)的背包中

3. 不把第0和第1个物品放入背包，但把第2个物品放入背包，然后考虑把[3...n-1]个物品（总共有n-3个物品）放入容量为C-w(2)的背包中

4. ...

   
   

所以以此类推，根据上述过程，是否可以把状态转移方程写为：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) ？

请问老师这样写出来的状态转移方程，是否本质上和课程中描述的一次考虑一件物品的转移方程相同呢？

谢谢老师！

Answer 1

liuyubobobo 2019-07-03 14:04:34

可以的：）

但是，你的这个转移方程，比我们在课程中介绍的转移方程复杂很多：）

你的这个状态转移方程转移的过程相当于是O(n)的，而课程中介绍的方法，转移过程是O(1)的（因为不管i是多少，只向两个状态转移。）

赞思考！：）

继续加油！：）

• 提问者 软件工程小白菜 #1

  非常感谢！

• 提问者 软件工程小白菜 #2

  但老师是想说我这个转移方程每次都转移O(n)？而课程中介绍的方法每次转移O(1)吗？

• liuyubobobo 回复 提问者 软件工程小白菜 #3

  哈哈哈 对对对 打错了 我改一下：）