使用python贪心算法和蛮力算法解决问题~~

发布网友发布时间：2022-04-25 05:54

共1个回答

热心网友时间：2022-04-18 07:46

# coding:utf-8 """定义一个函数，名字为sameSums(aList)，alist是一个整形list(限定重复元素不超过2个,排2f0e除这样的list，元素前后差为1，[4,5,6,7,8])，函数作用是判断能分成两组，使得两组数字的和相等。若可以择返回值是true，若不可以返回值是false。如下例：sameSums([4, 7, 6, 3]) --> True //4+6 = 10 and 7 + 3 = 10sameSums([3, 3]) --> TruesameSums([4, 12, 16]) --> True //4+12= 16 and 16sameSums([5, 1]) --> False 特别提示：这个题目，贪心算法只能计算上面这样的情况。这个题目，对初学者来说，有点难度，但稍微有点算法基础，编程思路，就不难。先讲一个故事：二个小孩儿时从树上采板栗，最后合并一堆，分板栗，采集一人选一个的分。假定人性是贪婪的，第一个先选的人，选最大的，第二个选的人，选次大的，一直循环下去。贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。这个题目：先将list从大到小排序，中间设置2个空的list，从大的开始选，下一次选的时候，需要比较一下和，如果谁的和小，再添加一个，直到最后一个元素。 """ def sameSums(int_list): """ www.iplaypy.com python教程 """ >>> sameSums([4, 7, 6, 3]) True >>> sameSums([3, 3]) True >>> sameSums([4, 12, 16]) True >>> sameSums([5, 1]) False """ new_lst = sorted(int_list, reverse=True) list1 = list() list2 = list() for n in new_lst: if sum(list1) < sum(list2): list1.append(n) else: list2.append(n) return sum(list1) == sum(list2) if __name__ == "__main__": import doctest doctest.testmod() lst = [3, 9, 10, 30, 8] print sameSums(lst)追问你好，谢谢您给出的想法与分析，请问可以把这道题的源代码（答案）给我吗？