数组的N折分区，每个分区中的总和相等

小编典典

数组的N折分区，每个分区中的总和相等

algorithm

给定一个整数数组a，两个数字N和M，返回一N组整数，a使每个组的总和为M。

例如，说：

a = [1,2,3,4,5]
N = 2
M = 5

然后，该算法可能返回[2, 3], [1, 4]，[5], [2, 3]或者可能返回其他算法。

我在这里可以使用哪些算法？

编辑：

我不知道这个问题是NP问题。因此，如果我提供有关特定场景的更多详细信息，可能会有所帮助：

因此，我试图创建一个“匹配”应用程序。给定团队N数量和每个团队的玩家数量M，应用程序将侦听客户的请求。每个客户请求都会提供该客户代表的许多玩家。因此，如果我需要由5名球员组成的2支球队，那么如果5个客户发送请求，每个请求分别代表1、2、3、4、5个球员，那么我的应用程序应该在客户[1, 4]和客户之间产生对决[2, 3]。它还可能会在[1, 4]和之间产生匹配[5]。我不在乎

一种暗示是，任何代表多于M或少于0玩家的客户都是无效的。希望这可以简化问题。

阅读 229

2020-07-28

共1个答案

小编典典

这是我自己的使用动态编程的Python解决方案。这里给出算法。

def get_subset(lst, s):
    '''Given a list of integer `lst` and an integer s, returns
    a subset of lst that sums to s, as well as lst minus that subset
    '''
    q = {}
    for i in range(len(lst)):
        for j in range(1, s+1):
            if lst[i] == j:
                q[(i, j)] = (True, [j])
            elif i >= 1 and q[(i-1, j)][0]:
                q[(i, j)] = (True, q[(i-1, j)][1])
            elif i >= 1 and j >= lst[i] and q[(i-1, j-lst[i])][0]:
                q[(i, j)] = (True, q[(i-1, j-lst[i])][1] + [lst[i]])
            else:
                q[(i, j)] = (False, [])

        if q[(i, s)][0]:
            for k in q[(i, s)][1]:
                lst.remove(k)

            return q[(i, s)][1], lst

    return None, lst

def get_n_subset(n, lst, s):
    ''' Returns n subsets of lst, each of which sums to s'''
    solutions = []
    for i in range(n):
        sol, lst = get_subset(lst, s)
        solutions.append(sol)

    return solutions, lst


# print(get_n_subset(7, [1, 2, 3, 4, 5, 7, 8, 4, 1, 2, 3, 1, 1, 1, 2], 5))
# [stdout]: ([[2, 3], [1, 4], [5], [4, 1], [2, 3], [1, 1, 1, 2], None], [7, 8])

2020-07-28