python回溯

2021/12/1 11:07:01

本文主要是介绍python回溯,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

# -*- coding: utf-8 -*-
"""
Spyder Editor

This is a temporary script file.
"""

bestV=0  #设置最好价值初始值为零
curW=0    #设置初始权重为零
curV=0      #设置初始权重价值为零
bestx=None    #设置初始选择为零
 
def backtrack(i):   #定义回溯算法
	global bestV,curW,curV,x,bestx #纳入全局变量
	if i>=n:            #如果i大于等于6,判断是否有更好的,有就替换,写出选择结果
		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=6
	c=5
	w=[5,3,2,2,3,1]
	v=[800,200,600,700,400,100]
	x=[False for i in range(n)]  #设置初始值均为false
	backtrack(0)
	print(bestV)
	print(bestx)
    

1400
[False, False, True, True, False, True]



这篇关于python回溯的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程