34.1-4

A questão consiste em dizer se o algoritmo de programação dinâmica feito na questão 16.2-2 para resolver o problema da mochila 0-1 onde os pesos são inteiros e a capacidade da mochila é também um inteiro dado W, algoritmo este de complexidade O(nW), é polinomial.

Resposta: não é polinomial.

Para ver isto, considere o tamanho da entrada:

Item da entrada	Tamanho
n	lg n
w(i), para i = 1, 2, ..., n	n . lg W'
c(i), para i = 1, 2, ..., n	n . lg C
W	lg W
Total	lg n + n . (lg W' + lg C) + lg W

Nota: aqui W' é o valor do maior peso e C o valor do maior custo.

Na complexidade O(nW), primeiro observamos que ela é na verdade Ө(nW), e depois vemos que, embora n seja polinomial no tamanho da entrada, o mesmo não ocorre com W, que pode ser exponencial no tamanho da entrada (a qual inclui apenas uma parcela lg W).