本文实例讲述了Python基于回溯法解决01背包问题。分享给大家供大家参考,具体如下:
同样的01背包问题,前面采用动态规划的方法,现在用回溯法解决。回溯法采用深度优先策略搜索问题的解,不多说,代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
bestV = 0
curW = 0
curV = 0
bestx = None
def backtrack(i):
global bestV,curW,curV,x,bestx
if i> = n:
if bestV<curV:
bestV = curV
bestx = x[:]
else :
if curW + w[i]< = c:
x[i] = True
curW + = w[i]
curV + = v[i]
backtrack(i + 1 )
curW - = w[i]
curV - = v[i]
x[i] = False
backtrack(i + 1 )
if __name__ = = '__main__' :
n = 5
c = 10
w = [ 2 , 2 , 6 , 5 , 4 ]
v = [ 6 , 3 , 5 , 4 , 6 ]
x = [ False for i in range (n)]
backtrack( 0 )
print (bestV)
print (bestx)
|
运行结果如下:
希望本文所述对大家Python程序设计有所帮助。
原文链接:http://blog.csdn.net/littlethunder/article/details/26621427