作者chun10396974 (pulse6974)
看板Python
标题[问题] list中选取最小和
时间Mon Nov 12 16:54:34 2018
题目是这样的 给定一个都是数字的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://webptt.com/cn.aspx?n=bbs/Python/M.1542012883.A.B4F.html
1F：→ djshen: 看起来是DP 11/12 17:21
2F：→ adrianshum: 大概想法： term n 不选取的最小总和= n+1 选取的最小 11/12 20:39
3F：→ adrianshum: 总和；n 选取的最小总和 = term n + min ( n+1 不选 11/12 20:39
4F：→ adrianshum: 取的最小总和, n+1选取的最小总和） 11/12 20:39
5F：推 kyrie77: DP ＋1 11/12 21:26