Problema da mochila - NP-completo, apesar da solução de programação dinâmica?

52

Problemas de mochila são facilmente resolvidos por programação dinâmica. A programação dinâmica é executada em tempo polinomial; é por isso que fazemos, certo?

Eu li que, na verdade, é um problema NP-completo, o que significa que provavelmente é impossível resolver o problema no problema polinomial.

Onde está meu erro?

Strin
fonte
5
Lembre-se de que o DP é polinomial no "tamanho da tabela". A tabela é exponencialmente grande para a mochila (veja a resposta de Kaveh).
Raphael

Respostas:

41

Problema da mochila é NP-complete quando os números são dados como binários números. Nesse caso, a programação dinâmica levará exponencialmente muitos passos (no tamanho da entrada, isto é, o número de bits na entrada) para finalizar .

Por outro lado, se os números na entrada forem dados em unário, a programação dinâmica funcionará em tempo polinomial (no tamanho da entrada).

Esse tipo de problema é chamado fracamente NP-complete .

2nnnnlgnO(n)=O(2lgn/2)

Esse tipo de algoritmo, ou seja, polinômio no maior número que faz parte da entrada, mas exponencial no comprimento da entrada é chamado pseudo-polinômio .

Kaveh
fonte
Mas pense nos objetos a serem colocados na mochila. Os objetos precisam ser inseridos e essa entrada deve ser polinomial com o número de objetos. Se os objetos forem suficientes, a entrada será polinomial com o tamanho do problema. Então, por que não posso dizer que o Problema da Mochila é um problema P em termos de tamanho da tabela? Estou errado?
Strin
mm2lgmm
Você pode dividir a entrada em entradas menores, cuja codificação binária tem um tamanho que termina o algoritmo em tempo polinomial e combina as soluções?
Char
@Kaveh "O tamanho da entrada é de aproximadamente 2 lg m" Eu não entendo de onde você tira essa peça. A relação entre m(tamanho da embalagem) e n(número de itens) é totalmente desconhecida, certo? E re "quando os números são dados como números binários" ... mas você não pode dizer isso para nada? Na maioria dos algoritmos, falamos sobre o tamanho da entrada na base 10. Por que falar sobre o binário aqui? E se você codifica em binário, octal, decimal, etc ... o actualnúmero de vezes que você itera pelo loop principal do algoritmo depende diretamente de ambos ne W.
The111
11
@ The111, acho que é melhor se você postar isso como uma nova pergunta e eu postarei uma resposta. Eu acho que sua pergunta é mais fundamental e há comentários não muito relacionados a essa questão.
Kaveh
33

A principal confusão está na diferença entre " tamanho " e " valor ".

" Tempo polinomial " implica em polinômio o tamanho da entrada.

" Tempo pseudopolinomial " implica em polinômio o valor da entrada. Pode ser mostrado (abaixo) que isso é equivalente a ser exponencial em relação ao tamanho da entrada.


NsizeNval

O(Nsizex)xN

O(Nvalx)xN

O(nW)W

Nsize=Logb(Nval)NvalbNval

Nval=bNsize

Nsize

O(bxNsize)b,xN

bcorso
fonte
7
Criou uma conta aqui apenas para agradecer muito! Somente após o seu exemplo eu finalmente entendi.
Inoryy 6/03/2014
2
Sua resposta supera todos, bravo!
Muhammad Razib 01/12/2015
11
Para adicionar a essa ótima resposta, podemos dizer que, se alterarmos o W de 100 para 101, o tamanho do problema não será aumentado, o tamanho será aumentado se adicionarmos outro bit ao W, o que o torna duas vezes maior, portanto a tabela tem o dobro de linhas e, portanto, com o aumento do tamanho em um, o tempo do problema é dobrado, por isso é exponencial.
Amém
@bcorso Suponha que você receba um valor N. E você teve que encontrar a soma dos números de 1 a N e usou o método for loop, que seria um algoritmo de tempo pseudopolinomial?
DollarAkshay
8

P=NP

Existem, no entanto, diferentes variantes (por exemplo, 0-1 Mochila e outras ) que podem ou não ter soluções em tempo polinomial ou boas aproximações. Mas isso não é o mesmo que o problema geral da mochila. Além disso, pode haver algoritmos eficientes que funcionam para instâncias específicas (famílias de) , mas esses algoritmos levarão mais tempo em outras instâncias.

Tocou.
fonte