def DecisionTree( weight_arr, value_arr, index, left_space ):
	if index == 0:
		if left_space >= weight_arr[index]:
			return value_arr[index]
		else:
			return 0
	without_index = DecisionTree( weight_arr, value_arr, index - 1, left_space )
	if weight_arr[index] > left_space:
		return without_index
	else:
		with_index = values[index] + DecisionTree( weight_arr, value_arr, index - 1, left_space -weight_arr[index] )
		return max( with_index, without_index )

weights = [ 1, 5, 3, 4 ]
values = [ 15, 10, 9, 5 ]
res = DecisionTree( weights, values, len( values ) - 1, 8 )

01背包 决策树模型 Python