Python练习题：从列表中选取任意个元素求和

Python练习题：从列表中选取任意个元素求和

一、问题

碰到一个比较好玩的问题，我有许多小额的发票，需要从这些发票中凑出一个指定的整数来。怎么去实现呢？

二、规划求解

在excel中，有一个功能是“规划求解”，具体可以参看链接：规划求解。 规划求解怎么算的，我也不知道，我们来看看用python怎么实现。

三、python实现

这些小额发票，我们可以用一个列表来表示。比如a = [1, 3, 5, 6, 8]。

那么这个列表的元素可能产生多少种组合呢？

由于列表里面每一个元素都可能有，也可能没有。

所以这里面就有2的5次方种变化。

a = [1, 3, 5, 6, 8]all_subset = [[]]for i in range(len(a)): for j in range(len(all_subset)): all_subset.append(all_subset[j]+[a[i]])print(all_subset)print(len(all_subset)) # 32

似乎我只需要对上面的二维数组里面每一个元素，即一维数组求和即可。列表中有5个数，有32种可能性，这么操作可行。但是，假如是10个数则有1024（2的10次方）种可能性，20个数就有1048576（2的20次方）种可能性，30个数则有1073741824（2的30次方）种可能性。组合的可能性可是指数翻番，电脑根本存不下这么长的列表。那就得再想其它办法。

现在的问题是，在没有这个长列表的情况下，我怎么去遍历这些所有组合呢。我们用多层嵌套的方式求解。

a = [1, 3, 5, 6, 8]ran2 = range(2)sum = 0for d0 in ran2: for d1 in ran2: for d2 in ran2: for d3 in ran2: for d4 in ran2: data = a[0]*d0 + a[1]*d1 + a[2]*d2 + a[3]*d3 + a[4]*d4 sum += 1print(sum) # 32

这样我们就不用存这个长列表，只要把每一个data跟设定的总数进行对比即可。但是问题又来了，如果给了我30张发票，我要写30个嵌套循环吗？那画面简直无法想象。

我们注意到，列表里面每个元素，只有两种状态，即有和没有。那么可以再创建一个列表，表示状态，0表示没有，1表示有。即

a = [1, 3, 5, 6, 8]coefficient = [0, 0, 0, 0, 0]

这样就只需要更改coefficient里面每个元素的状态即可。为了实现coefficient这个列表各种可能性，我们可以采用把数字转为二进制，然后将二进制数每个数字位分开的方式。 代码如下。

a = [1, 3, 5, 6, 8]for i in range(0, 2**len(a)): coefficient = list(str(bin(i))[2:].rjust(len(a), '0')) print(coefficient)

结果如下：

['0', '0', '0', '0', '0']['0', '0', '0', '0', '1']['0', '0', '0', '1', '0']['0', '0', '0', '1', '1']['0', '0', '1', '0', '0']....['1', '1', '1', '1', '0']['1', '1', '1', '1', '1']

这样就只需要把列表a和列表coefficient的每个元素相乘累加即可。

四、代码

最后呈现的代码如下，我有29张发票，要求得到的值是180。

'''学习中遇到问题没人解答？小编创建了一个Python学习交流群：711312441寻找有志同道合的小伙伴，互帮互助,群里还有不错的视频学习教程和PDF电子书！'''import timefrom functools import reduce# 原列表nums = [1.68, 37.27, 14.78, 12.84, 15.26, 4.86, 10.06, 25.6, 8.42, 20.27, 6.46, 29.68, 6.13, 18.48, 4.98, 7.88, 4.77, 8.61, 5.75, 4.3, 7.76, 3.13, 11.11, 5.1, 2.91, 3.55, 6.45, 55.27, 8.76]# 期待求和的值expect_data = 180# 对数组进行排序nums.sort()# 缩小数组范围，将比设定值大的元素抛弃narrow_nums = []for i in nums: if i > expect_data: break narrow_nums.append(i)# 把数组倒序narrow_nums.sort(reverse=True)start_time = time.time()# 开始计算for i in range(0, 2**len(narrow_nums)): # 将循环的值转变为参数列表 nums_coefficient = list(str(bin(i))[2:].rjust(len(narrow_nums), '0')) # 将参数列表和原数组进行乘积运算得到新的列表 combine_list = list(map(lambda x: x[0] * int(x[1]), zip(narrow_nums, nums_coefficient))) # 对列表进行求和取值 sumdata = reduce(lambda x, y: x + y, combine_list) if abs(sumdata - expect_data) < 1e-6: print(list(filter(lambda x: x > 0, combine_list))) breakend_time = time.time()print('运算了{}次，耗时{}'.format(i, round(end_time - start_time, 2)))

以下是结果：

[20.27, 18.48, 14.78, 12.84, 11.11, 10.06, 8.76, 8.61, 8.42, 7.88, 7.76, 6.46, 6.45, 5.75, 5.1, 4.98, 4.86, 4.77, 4.3, 3.55, 3.13, 1.68]运算了29359101次，耗时591.0

五、总结

介绍了如何将多层嵌套转化为一维数组进行运算

本文采用暴力破解，耗时较久。抛砖引玉，欢迎大家留言，提供节省时间复杂度的算法。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。