→ djshen: 看起來是DP 11/12 17:21
→ adrianshum: 大概想法： term n 不選取的最小總和= n+1 選取的最小 11/12 20:39
→ adrianshum: 總和；n 選取的最小總和 = term n + min ( n+1 不選 11/12 20:39
→ adrianshum: 取的最小總和, n+1選取的最小總和） 11/12 20:39
推 kyrie77: DP ＋1 11/12 21:26
題目是這樣的 給定一個都是數字的list
對於每個數字可以決定選或不選
但是不能有相鄰的兩個都沒有被選到
example1:[10,12,7,21,8]
10+7+8=25
有最小值
example2:[155,44,52,58,250,225,109,178]
44+58+225+109=436
有最小值
剛開始以為是用數學方法來做
於是便以兩個一組、三個一組、四個一組來討論選取的方式
但是實際下去操作會發現前面怎麼取都無法顧及到後面的選取
(因為不知道後面的數的大小關係)
即一定要顧慮到所有的數
所以改採recursive的方法來窮舉
b=[]
def help_santa(a):
n=len(a)
plus(a,0,0,n)
return min(b)
def plus(a,s,t,n):
if n==0:
b.append(t)
elif s==1:
plus(a,0,t+a[-n],n-1)
else:
plus(a,0,t+a[-n],n-1)
plus(a,1,t,n-1)
其中函數的第二個值為1代表上一個被跳過所以下一個值必須要選
但是這個做法在輸入的list很大的時候會產生記憶體不足的現象
因此請教各位大大有沒有更好的寫法？
感謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.196.49
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1542012883.A.B4F.html