动态规划,求值并找具体位置

数据结构及算法 | 2018-10-21 10:08:44 | 阅读 131 次 | 评论(0)
递归实现 动态规划 并找出一个最优解
 从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) 


文章评论,共0条
游客请输入验证码
浏览163610次
最新评论