阵列的每个分区中等于总和N倍分区 [英] N-fold partition of an array with equal sum in each partition

问题描述

由于整数数组 A ，两个数字 N 和 M ，返回 N 组整数从 A 使得每组款项中号。

Given an array of integers a, two numbers N and M, return N group of integers from a such that each group sums to M.

举例来说，说：

• A = [1,2,3,4,5]
• N = 2
• M = 5

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

则算法可以返回 [2，3]，[1,4] 或 [5]，[2，3] 或其它可能的。

Then the algorithm could return [2, 3], [1, 4] or [5], [2, 3] or possibly others.

我可以用在这里是什么算法？

What algorithms could I use here?

编辑：

我不知道这个问题是NP完全。因此，也许这将有助于如果我提供了我的具体方案的更多细节：

I wasn't aware that this problem is NP complete. So maybe it would help if I provided more details on my specific scenario:

所以我想创造一个匹配式的应用程序。鉴于球队的数量 N 和每队玩家数量 M ，应用程序监听客户端请求。每个客户端请求会给一些玩家在客户端重新presents。所以，如果我需要2队的5名球员，那么如果5个客户端发送请求，每个重presenting 1，2，3，4，分别为5名球员，那么我的应用程序应生成客户端之间的比赛了 [1,4] 和客户端 [2，3] 。它也可能产生的 [1,4] 和 [5] 匹配行动;我真的不关心。

So I'm trying to create a "match-up" application. Given the number of teams N and the number of players per team M, the application listens for client requests. Each client request will give a number of players that the client represents. So if I need 2 teams of 5 players, then if 5 clients send requests, each representing 1, 2, 3, 4, 5 players respectively, then my application should generate a match-up between clients [1, 4] and clients [2, 3]. It could also generate a match-up between [1, 4] and [5]; I don't really care.

一个含义是，比 M 或小于 0 玩家任何客户端重新presenting更是无效的。希望这可以简化问题。

One implication is that any client representing more than M or less than 0 players is invalid. Hope this could simplify the problem.

推荐答案

下面是一个使用动态规划我自己的Python的解决方案。算法给出<一href="http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution"相对=nofollow>这里。

Here is my own Python solution that uses dynamic programming. The algorithm is given here.

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])

这篇关于阵列的每个分区中等于总和N倍分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！