格,广场舞中国冲冲冲:背包问题算法

来源:百度文库 编辑:中科新闻网 时间:2024/03/29 13:37:22
用回溯法的思想,用战的非递归方法实现背包问题(简化的,没有价值,求出所有能装满背包的解),只要讲一讲思想,要仔细点哦!!!!

首先建立一个堆栈,里面存放的是物品信息。算法开始后,按照一定的次序存放物品,每放进去一个物品,就检查是否越界,如果没越界,就继续选择物品放入(入栈);如果越界,就退出当前物品(出栈),当正好装满一个背包时,记录当前栈到一个数组,并退出顶端物品(出栈),往后放物品……一直到栈空为止,这样可以找到所有最佳存放方法。