Étant donné un ensemble de n entiers, liste tous les sous-ensembles possibles avec la somme & gt; = k

Donné un non triés ensemble des entiers sous forme de tableau, de trouver tous les sous-ensembles possibles dont la somme est supérieure ou égale à un const integer k,
par exemple:- Notre ensemble {1,2,3} et k=2

Les sous-ensembles possibles:-

 {2},
 {3},
 {1,2},
 {1,3},
 {2,3}, 
 {1,2,3}

Je ne peux que penser d'un algorithme naïf qui répertorie tous les sous-ensembles de vérifier si la somme de sous-ensemble est >=k ou pas, mais ses un algorithme exponentiel et la liste de tous les sous-ensembles nécessite O(2^N). Puis-je utiliser la programmation dynamique pour résoudre en temps polynomial?

source d'informationauteur Hidetoshi

  1. 9

    Liste de tous les sous-ensembles va être encore O(2^N) parce que dans le pire des cas, vous pouvez avoir encore de la liste de tous les sous-ensembles en dehors de la vide.

    De la programmation dynamique peut vous aider à compter le nombre de jeux qui ont sum >= K

    Vous allez bottom-up de garder une trace de combien de sous-ensembles de résumé d'une certaine valeur de la gamme [1..K]. Une approche de ce genre seront O(N*K) qui va être applicable que pour les petites K.

    L'idée avec la programmation dynamique la solution est illustré par un exemple. Considérez la situation. Suppose que vous savez que, sur tous les ensembles composés de la première i éléments vous savez que t1 somme de 2 et t2 somme de 3. Disons que la prochaine i+1 élément est 4. Compte tenu de tous les jeux existants, nous pouvons construire tous les nouveaux jeux, soit en ajoutant l'élément i+1 ou de le laisser sortir. Si nous ne nous obtenir t1 des sous-ensembles d'un montant total de 2 et t2 des sous-ensembles d'un montant total de 3. Si nous ajoutons ensuite, il nous obtenir t1 des sous-ensembles d'un montant total de 6 (2 + 4) et t2 que cette somme 7 (3 + 4) et un sous-ensemble qui contient exactement i+1 qui sommes à 4. Qui nous donne le nombre de sous-ensembles d'un montant total de (2,3,4,6,7) composé de la première i+1 éléments. Nous continuons jusqu'à ce que N.

    En pseudo-code, cela pourrait ressembler à quelque chose comme ceci:

    int DP[N][K];
int set[N];

//go through all elements in the set by index
for i in range[0..N-1]
   //count the one element subset consisting only of set[i]
   DP[i][set[i]] = 1

   if (i == 0) continue;

   //case 1. build and count all subsets that don't contain element set[i]
   for k in range[1..K-1]
       DP[i][k] += DP[i-1][k]

    //case 2. build and count subsets that contain element set[i]
    for k in range[0..K-1] 
       if k + set[i] >= K then break inner loop                     
       DP[i][k+set[i]] += DP[i-1][k]

//result is the number of all subsets - number of subsets with sum < K
//the -1 is for the empty subset
return 2^N - sum(DP[N-1][1..K-1]) - 1
  2. 6

    Puis-je utiliser la programmation dynamique pour résoudre en temps polynomial?

    Pas. Le problème est encore plus difficile que @amit (dans les commentaires) mentionne. Trouver s'il existe un sous-ensemble qui sommes à un k est le subset-sum problèmequi est NP-dur. Au lieu de cela, vous vous demandez pour combien de solutions sont égale à un certain k, qui est beaucoup plus difficile de classe de P#. En outre, votre problème est un peu plus difficile car il faut non seulement compter, mais d'énumérer tous les sous-ensembles de k et cibles < k.

  3. 1

    Si k est 0, et chaque élément de l'ensemble est positive, alors vous n'avez pas le choix, mais à la sortie de chaque sous-ensemble, de sorte que la limite inférieure de ce problème est de O(2N) -- le temps nécessaire pour produire la sortie.

    Sauf si vous savez quelque chose de plus au sujet de la valeur de k que vous n'avez pas dit de nous, il n'y a pas plus rapide solution générale que de simplement vérifier chaque sous-ensemble.