背包问题的求解,麻烦高手指点一下？谢谢

怎么用回溯法的问题求解？需要使用栈~~~
   。。。小弟我对回溯法的认识 欠浅~~~~。。。有劳各位高手帮帮忙？

6 个解决方案

#1

背包是什么？闭包么？
栈是一种数据结构，跟回溯没有必然的联系。
昨天看见一个迷宫问题的解法，你可去试试，很典型的递归：
http://topic.csdn.net/u/20100112/14/f9fe8a23-7694-4104-b10b-df7d03f3080b.html

#2

背包是：假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , … , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + … + wn=T，要求找出所有满足上述条件的解。

可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品"太大"不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明"刚刚"装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。

#3

LZ问的是背包问题，一个经典的数据结构问题

#4

csdn有很多关于这样的问题的讨论。
比如，求出1到20中，所有和为30的数的组合。
其实跟你这个背包是一个意思。
http://topic.csdn.net/u/20091228/23/5d351d1d-86ae-430f-9e5a-b1a418e1e2f3.html
http://topic.csdn.net/u/20100105/17/bc02a6d5-7dbb-42cc-aa49-d8c3921ec386.html

#5

http://topic.csdn.net/u/20100106/15/af894fbe-8193-4667-b218-3da2ed2b9ecc.html

#6

http://www.docin.com/p-18392285.html
专门讲01背包问题的回溯算法的