继续实现算法导论里面的题目和算法

#算法导论第四章:动态规划题目:切钢条
'''问题:给定一个长度为n的钢条,和一个价格表,问切割方案s.t.受益最大
切割表:
长度:1 2 3 4 5  6  7   8  9 10
价格:1 5 8 9 10 17 17 20 24 30

'''
#作为动态规划的本质还是要先写出地柜的版本.然后改地推即可.
#首先做出数据:
a=[]
a.append([1,2,3,4,5,6,7,8,9,10])
a.append([1,5,8,9,10,17,17,20,24,30])
print (a)
#同样对他进行计数
#先写一个水的版本,把方案利润最后的答案打印出来即可.
count=0
def fangan(n):
 global count
 count+=1
 tmp=0#用来储存所有的方案的利益
 
 if n in a[0]:
      for i in range(len(a[0])):
           if a[0][i]==n:
                tmp=(a[1][i])
                break
 for i in range(1,n//2+1):
      b=fangan(i)+fangan(n-i)
      if b>tmp:
       tmp=b
 return tmp
print (fangan(7))
print ('递归版本的计数是:')
print (count)
#下面写把切割方案也写出来.这个书中没有体现,感觉有点难的!
def fangan(n):
 tmp=[0,[0]]#用来储存所有的方案的利益
 if n in a[0]:
      for i in range(len(a[0])):
           if a[0][i]==n:
                tmp=[a[1][i],[n]]
                
                break
 for i in range(1,n//2+1):
      b=fangan(i)[0]+fangan(n-i)[0]
      qiege=fangan(i)[1]+fangan(n-i)[1]
      if b>tmp[0]:
       tmp[0]=b
       tmp[1]=qiege
 return tmp
print (fangan(10))
#然而利用函数的多返回值还是成功写出来了.注意这里的返回值用list实现,用tuple修改不了所以不行.


#然而如果老板要求获得所有最好的方案呢?比如fangan(7)就应该有2个解7=1+6=2+2+3



#继续实现上面的目标:
def fangan(n):
 tmp=[0,[0]]#用来储存所有的方案的利益
 if n in a[0]:
      for i in range(len(a[0])):
           if a[0][i]==n:
                tmp=[a[1][i],[n]]
                
                break
 for i in range(1,n//2+1):
      b=fangan(i)[0]+fangan(n-i)[0]
      qiege=fangan(i)[1]+fangan(n-i)[1]
      if b>tmp[0]:
       tmp[0]=b
       tmp[1]=qiege

 for i in range(1,n//2+1):
      b=fangan(i)[0]+fangan(n-i)[0]
      qiege=fangan(i)[1]+fangan(n-i)[1]
      if b==tmp[0]:
          tmp.append(sorted(qiege))
 #去重
 k=[]
 for i in range(2,len(tmp)):
         
         if tmp[i] in tmp[:i]:
             
              k.append(i)#记录需要弹出的index

## for i in k:
##     tmp.pop(i)
 #不知道为什么这个去重有bug!??但是基本不难了知道错哪里了,pop一次index就变了!!!
 #所以还是要用for来重新建立就行了.
 c=[]
 for i in range(len(tmp)):
     if i not in k:
         c.append(tmp[i])
 return c
print (fangan(7))

#想法是直接在递归过程中,建立表,然后每一次递归调用都先搜索表中是否存在,
#从而实现动态规划.下面来实现.



print ('下面是动态规划版本')

#首先还是做这个只返回最大利益的这个简单例子.b作为表格来储存每一个递归结果.
#简单的写出来,然后为了讨论效率加一个count来计数
b=[0]*len(a[0])
count=0
def fangan(n):
 global count
 count+=1
 global b
 if b[n-1]!=0:
     return b[n-1]
 tmp=0#用来储存所有的方案的利益
 if n in a[0]:
      for i in range(len(a[0])):
           if a[0][i]==n:
                tmp=(a[1][i])
                break
 for i in range(1,n//2+1):
      c=fangan(i)+fangan(n-i)
      if c>tmp:
       tmp=c
 
 b[n-1]=tmp
 return tmp
print (fangan(7))
print('动态规划版本的计数是')
print (count)