作者在 2018-10-21 10:08:44 发布以下内容
递归实现 动态规划 并找出一个最优解
从V中选一些数据，使之和与另一给定值j最接近，（不大于j)对于V中的某个元素，用选或不选进行分析，选用此数时放右子树
不选时放左子树，并进行递归 。
# -*- coding:utf-8-*-
###从V中选一些数，使之和与另一给定值j 最接近（不大于j）。 动态规划时，对于V中的某个元素，选或不选进行递归，选此数时放右子树，不选放左子树
###利用二叉树递归处理，动态规划 v ，并把每个右子树的值保存在的r_list中。
v=[11,91,12,71,97,5,23,9,21,73,34]
r_list=[0,0]
def knap(i,j):
if(i==-1 or j<=0):
return 0
else:
left=knap(i-1,j)
right=knap(i-1,j-v[i])+v[i]
if(j>=v[i] and right>=left):
r_list.append([i,right])
return right
else:
return left
###处理递归保存在右子树的值（除重，并除首值）
val=knap(10,431)
leng=len(r_list)
sel=list()
def deal_list(r_list):
for t in r_list:
if not t in sel:
sel.append(t)
sel.remove(sel[0])
###从列表V中找位置
deal_list(r_list)
print(sel)
leng=len(sel)
def find_num(v,sel,val,leng):
while val:
leng=leng-1
if sel[leng][1]==val:
print("value in v=",v[sel[leng][0]], ",v's index=",sel[leng][0])
val=val-v[sel[leng][0]]
find_num(v,sel,val,leng)
print("max=",val)
