4

给定一个整数数组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，应用程序会侦听客户端请求。每个客户端请求都会给出客户端代表的玩家数量。因此，如果我需要 2 支 5 名球员组成的球队，那么如果 5 个客户端发送请求，每个请求分别代表 1、2、3、4、5 名球员，那么我的应用程序应该在 clients[1, 4]和 clients之间生成一场比赛[2, 3]。它还可以在[1, 4]和之间产生匹配[5]；我真的不在乎。

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

4

3 回答 3

2

这似乎是子集和问题的一种变体。由于这个问题是 np 完全的，没有进一步的约束就没有有效的算法。

请注意，已经很难找到元素总和为 的原始集合的单个子集M。

于 2013-05-07T09:08:17.057 回答
2

人们太容易放弃 NP 完全问题。仅仅因为一个问题是 NP 完全的，并不意味着在一般情况下没有越来越多有效的算法。也就是说，您不能保证对于所有输入都有一个可以比蛮力搜索更快地计算的答案，但是对于许多问题，您当然可以使用比对大多数输入的完整搜索更快的方法。

对于这个问题，肯定有“反常”的数字集会导致最坏情况的搜索时间，因为可能会有一个很大的整数向量，但只有一个解决方案，你最终必须尝试大量的组合。

但是对于非反常集合，可能有很多解决方案，并且“绊倒”良好分区的有效方法将比 NP 时间运行得快得多。

你如何解决这个问题在很大程度上取决于你期望的更常见的参数。如果整数都是正数，或者是否允许负数，它也会有所不同。

在这种情况下，我会假设：

  1. N相对于向量的长度很小
  2. 所有整数都是正数。
  3. 整数不能重复使用。

算法：

  1. 对向量 v 进行排序。
  2. 消除大于 M 的元素。它们不能成为任何解决方案的一部分。
  3. 将 v 中剩余的所有数字相加，除以 N。如果结果小于 M，则无解。
  4. 创建一个与 v 大小相同的新数组 w。对于每个 w[i]，将 v[i+1 - end] 中的所有数字相加

因此，如果 v 为 5 4 3 2 1，则 w 将为 10、6、3、1、0。

虽然您还没有找到足够的集合：

  1. 选择最大的数 x，如果它等于 M，则发出一个只有 x 的解集，并将其从向量中删除，从 w 中删除第一个元素。

还是不够套？（可能），然后在您没有找到足够的集合时再次：

  1. 求解理论是 ([a,b,c], R )，其中 [a,b,c] 是 v 和余数 R 的部分元素集。R = M-sum[a,b,c]。扩展理论是将一个数字添加到部分集合中，然后从 R 中减去该数字。当您扩展理论时，如果 R == 0，这是一个可能的解决方案。

像这样递归地创建理论：循环遍历元素 v，因为 v[i] 创建了理论，( [v[i]], R )，现在递归地从 v 的一部分扩展每个理论。二分搜索到 v 以找到等于或小于 R 的第一个元素，v[j]。从 v[j] 开始，用 v 的元素从 j 到 R > w[k] 扩展每个理论。

从 v[j] 到 v[k] 的数字是唯一用于扩展理论并且仍然使 R 为 0 的数字。大于 v[j] 的数字将使 R 为负数。比 v[k] 小，并且数组中不再有任何数字，即使您使用它们全部使 R 为 0

于 2013-05-07T19:35:12.527 回答
0

这是我自己的使用动态编程的 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])
于 2013-05-08T02:57:45.980 回答