#---*--- encoding=utf-8 ----*-----
#----------------------------
#买书问题
#贪心算法是失效的，5,3->5,4单个并不是最优的，这次选择会影响下一次的选择的
#比如反例：(5,5,5,3,3)贪心的策略为(5,5,5,3,3)--133.2,
#改进的贪心策略为(5,5,4,4,3)--132.8,
#而实际的最优的策略为(5,4,4,4,4)--132.4
#动态规划多采用递归实现，但是递归的性能不是很好，有时间和空间的复杂度的占用
#注意递归的终止条件和循环变量的控制
#----------------------------
import copy
def buy_book_question(y1,y2,y3,y4,y5):
bookList=[]
bookList.append(y1)
bookList.append(y2)
bookList.append(y3)
bookList.append(y4)
bookList.append(y5)
bookList.sort(reverse=True)
y1,y2,y3,y4,y5=bookList[0],bookList[1],bookList[2],bookList[3],bookList[4]
# solution=00000
if len(bookList)==5:
if y1==y2==y3==y4==y5==0:
return 0
else:
if y5>=1:
x1=5*8*0.75+buy_book_question(y1-1,y2-1,y3-1,y4-1,y5-1)
# solution=y1*10000+y2*1000+y3*100+y4*10+y5
else:
x1=10**10
if bookList[3]>=1:
x2=4*8*0.8+buy_book_question(y1-1,y2-1,y3-1,y4-1,y5)
# solution=y1*10000+y2*1000+y3*100+y4*10+y5
else:
x2=10**10
if bookList[2]>=1:
x3=3*8*0.9+buy_book_question(y1-1,y2-1,y3-1,y4,y5)
# solution=y1*10000+y2*1000+y3*100+y4*10+y5
else:
x3=10**10
if bookList[1]>=1:
x4=2*8*0.95+buy_book_question(y1-1,y2-1,y3,y4,y5)
# solution=y1*10000+y2*1000+y3*100+y4*10+y5
else:
x4=10**10
if bookList[0]>=1:
x5=8+buy_book_question(y1-1,y2,y3,y4,y5)
# solution=y1*10000+y2*1000+y3*100+y4*10+y5
else:
x5=10**10
minVal=min(x1,x2,x3,x4,x5)
# print solution
return minVal
else:
return 0
def pass_reference_param(bookList):
bookList[5].append("*")
bookList[5][3].append("i love you")
print bookList
if __name__ == '__main__':
bookList=[5,5,5,3,3,[1,2,3,[]]]
minVal=buy_book_question(5,5,5,3,3)
xx=xx=copy.copy(bookList)
print id(xx[5])
print id(bookList[5])
pass_reference_param()
print minVal
print bookList