4

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.

For example, say:

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

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

What algorithms could I use here?

Edit:

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

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.

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

4

3 に答える 3

2

人々は NP 完全問題をあまりにも簡単にあきらめてしまいます。問題が NP 完全であるからといって、一般的なケースで効率の良いアルゴリズムも悪いアルゴリズムも存在しないという意味ではありません。つまり、すべての入力に対してブルート フォース検索よりも高速に計算できる答えがあることを保証することはできませんが、多くの問題については、ほとんどの入力の完全検索よりも高速な方法を確実に使用できます。

この問題では、整数の大きなベクトルが存在する可能性があるため、最悪の場合の検索時間をもたらす「ひねくれた」数のセットが確かに存在しますが、解決策は 1 つしかなく、非常に多数の組み合わせを試す必要があります。

しかし、ひねくれていないセットの場合、おそらく多くの解決策があり、適切なパーティショニングを「つまずかせる」効率的な方法は、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[i] が理論を作成するように、要素 v をループします ( [v[i]], R ), そして、v の一部から各理論を再帰的に拡張します。 R 以下の最初の要素 v[j]。v[j] から始めて、j から R > w[k] まで v の要素で各理論を拡張します。

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 に答える