状态及状态转移的定义

Question

老师，你好.我将状态以及状态转移定义成下面这种形式可以吗

F（n，C）=max (  v(0)+F( n-1,C-w(0) ) , v(1)+F( n-1,C-w(1) ) , v(2)+F( n-1,C-w(2) )  ........ v(i)+F( n-1,C-w(1) ) ,v(n-1)+F( n-1,C-w(n-1) ) )

将F（n，C）的问题转换成F(n-1,C-w(i)), 递归终止的条件就是当选择的物品重量＞背包剩余容量的时候，递归并不是都要递归到底，所以有些物品也就没有办法放入背包，请老师原谅我编码能力实在太差...

Answer 1

liuyubobobo 2018-04-19 04:11:37

似乎有一些问题，你的状态转移中，每次都一定会拿出一个物品，最终得到的是这些物品的一个排列。但是背包问题的解释物品的组合，是选择拿哪些物品，不拿哪些物品。

或者可能我没有完全理解你的思路？把代码写出来试试看？：）

• 提问者 慕粉3924834 #1

  老师，我简单画了个图，感觉这思路类似于递归回溯，麻烦老师看一下。。。
  在递归的过程中可能第一层或者第二层就结束了，所以并不是把每个物品都放进去。

• liuyubobobo 回复 提问者 慕粉3924834 #2

  ok，看到了你的补充说明。从问题解决的角度是ok的。不过这是一个回溯的解决问题的过程，无法利用重叠子问题和最优子结构的性质，实现出来的复杂度是指数级的，而不像动态规划的解法，可以得到多项式的解：）

• 提问者 慕粉3924834 回复 liuyubobobo #3

  嗯嗯，谢谢老师，
  但是感觉最优子结构是存在的，max()函数就是把每一层的最优解求出来，然后返回给上一层

点开查看后面1条评论