将整数数组进行m等分,使得每一个部分的和相等且m最大

我对这个问题的解法是递归着解决的,首先对原始数组进行排序,然后我们首先选择m的大小,注意这里题目没有说明是否是正整数,如果是:那么最大的m一定小于(数组的和)/(数组最大的元素),否则就要从数组的元素个数开始枚举:

假设sum是数组元素和,我们首先判断m是不是可以被sum整除,如果不是,跳过.否则可以开始判断m到底能不能等分。我们对问题进行分解:[1]我们可以首先求出一个数组的子集使得它满足和为summ$frac{sum}{m}$[2]找到以后递归的处理剩下的元素

怎么找是不是存在这样一个集合呢?如果直接枚举显然复杂度极高。这里就用到了前面的排序结果了,我们就先求包含最大元素的那个集合,如果这个集合存在,那么才继续往下做,,否则就失败了。这样比起我们找一个满足条件的集合这样的目标,这个目标显然要清晰很多。这就是对目标进行改造,因为我们的最终目的是m等分,那么显然每一个元素都要包含在某一个集合里面,从而不妨选择一个进行处理。如果这里的目标是:是否存在一个这样的集合,那么我们就只有枚举了(当然排序以后再枚举,不是暴力枚举).

具体思路是:先拿出第一个元素,然后从最小的开始往大的方向遍历,直到这些元素加起来等于目标。这样做的好处是:如果加起来的值超过了目标,就直接结束这一次的循环(只有当前所有元素均为正整数的时候可以进行这个优化)。最后如果发现一个空集合,直接返回[]。

def Test(array,target):
    if len(array)==0:
        return []

    first = array[0]
    length = len(array)
    local_sum = first

    for i in range(length,0,-1):
        j = i

        can_optimalize = True if array[-1]<0 else False
        not_advanced_break = can_optimalize or (local_sum<=target)

        while j > 0 and not_advanced_break:#if any negative integer,cannot break in advance 

            if local_sum==target:
                first_set = [first]
                first_set.extend(array[j:length])
                remain_set = array[1:j]
                sub_ret = Test(remain_set,target)

                if sub_ret!=None:
                    ret = [first_set]
                    ret.extend(sub_ret)
                    return ret

            j -= 1
            local_sum += array[j]

    return None

def FindM(array):
    array_sum = sum(array)
    # = array_sum // max(array)
    array_ = sorted(array,reverse=True)

    for m in range(len(array_),0,-1):
        if array_sum%m == 0:
            ret = Test(array_,array_sum//m)
            if ret:
                print(ret)
                return

FindM([3,2,4,3,6,7,-1])

就这个程序的细节来说一说我关于编程习惯的一些思考吧,今天看了王垠的<编程的智慧>,感觉其中大多数是很有道理的(当然少数不是很清楚,也不敢妄加评论)。写程序最重要的是可读性,所以必须要尽可能的符合自己的直观思维,否则过一段时间自己都读起来比较费力了。因此以前一些可以写在一行的代码分开来写,目的是为了好懂,易懂,减少自己在debug时候的脑力消耗。很多时候节省一两行代码反而得不偿失,因为有些地方逻辑不直观每一次review都要想一下,这样积累下来的消耗是比较大的。

所以我在判断是不是需要提前退出这个循环的时候,将终止条件not_advanced_break 拆分开来写,就是要把当前所有元素是不是正数以及是不是累计和小于target这两个条件清晰的组合起来！另外我们要注意一个corner case,有可能当前的第一个元素自己单独组成一个集合,所以必须要考虑到这种情况。那么第一次的时候就不能够有任何的元素加进来.所以我的办法是将累积求和这个操作放到循环的后面进行。同时j的初始值也需要变化(从n开始而不是n-1)。