Empacotamento de conjuntos
Empacotamento de conjuntos é um clássico NP-completo problema em complexidade computacional teoria e análise combinatória, e foi um dos Karp 21 problemas NP-completos.

Suponha que temos um conjunto finito "S" e uma lista de subconjuntos de "S". Então, problema de empacotamento de conjuntos pergunta se algum conjunto com "k" subconjuntos da lista são dois a dois disjuntos (em outras palavras, não há dois compartilham um elemento).

Mais formalmente, dado um universo  formula_1 e uma família formula_2 de subconjuntos de formula_1, um "empacotamento "é uma subfamília formula_4 
de conjuntos de tal forma que todos os conjuntos em formula_5 são disjuntos dois a dois, e o tamanho do pacote é formula_6. No problema de decisão de empacotamento de conjuntos, a entrada é um par formula_7 e um inteiro formula_8; a questão é se há um pacote de conjuntos de tamanho formula_8 ou mais. No problema de otimização de empacotamento de conjuntos, a entrada é o par formula_7, e a tarefa é encontrar um pacote de conjuntos que utilize a maioria dos conjuntos. 

O problema está, claramente, em NP, uma vez que, dado "k" subconjuntos, podemos facilmente verificar que eles são pares disjuntos em tempo polinomial.

A versão otimizada do problema, o máximo empacotamento de conjuntos, pede-lhe o número máximo de pares disjuntos conjuntos na lista. É um problema de maximização, que pode ser formulado, naturalmente, como um programa linear inteiro, pertence à classe de problemas de empacotamento, e o seu dual programa linear é o problema da cobertura de conjuntos.
Q215206
NP-completo
MISC
Q5157286
complexidade computacional teoria
Concept
Q76592
análise combinatória
Concept
Q215382
disjuntos
Concept
Q3262192
problema de decisão de empacotamento de conjuntos
Concept
Q984063
problema de otimização de empacotamento de conjuntos
Concept
Q628036
NP,
MISC
Q846354
tempo polinomial
MISC
Q984063
versão otimizada
Concept
Q202843
programa linear inteiro
Concept
Q475603
Empacotamento de conjuntos
Concept
+21^^http://www.w3.org/2001/XMLSchema#decimal
21
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+4^^http://www.w3.org/2001/XMLSchema#decimal
4
NUMBER
+5^^http://www.w3.org/2001/XMLSchema#decimal
5
NUMBER
+6^^http://www.w3.org/2001/XMLSchema#decimal
6
NUMBER
+7^^http://www.w3.org/2001/XMLSchema#decimal
7
NUMBER
+8^^http://www.w3.org/2001/XMLSchema#decimal
8
NUMBER
+8^^http://www.w3.org/2001/XMLSchema#decimal
8
NUMBER
+7^^http://www.w3.org/2001/XMLSchema#decimal
7
NUMBER
instance of