PTT數位生活區 / Python

[問題] list中選取最小和

看板Python作者 (pulse6974)時間6年前 (2018/11/12 16:54), 編輯推噓1(1推 0噓 4→)
留言5則, 3人參與, 6年前最新討論串1/2 (看更多)
題目是這樣的 給定一個都是數字的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
→
11/12 17:21, 6年前 , 1F
看起來是DP
11/12 17:21, 1F
→
11/12 20:39, 6年前 , 2F
大概想法： term n 不選取的最小總和= n+1 選取的最小
11/12 20:39, 2F
→
11/12 20:39, 6年前 , 3F
總和；n 選取的最小總和 = term n + min ( n+1 不選
11/12 20:39, 3F
→
11/12 20:39, 6年前 , 4F
取的最小總和, n+1選取的最小總和）
11/12 20:39, 4F
推
11/12 21:26, 6年前 , 5F
DP ＋1
11/12 21:26, 5F
‣ 更多 chun10396974 的文章
文章代碼(AID): #1RwJ_JjF (Python)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共2篇)
Python 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 chun10396974 的文章
文章代碼(AID): #1RwJ_JjF (Python)