# -*- 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]