Problema da mochila

Exemplo de um problema knapsack unidimensional (constração): quais caixas devem ser escolhidas para maximizar a quantidade de dinheiro, mantendo o peso total abaixo ou igual a 15 kg? Um problema constrangido múltipla poderia considerar tanto o peso e o volume das caixas.
(Solução: se algum número de cada caixa estiver disponível, então três caixas amarelas e três caixas cinzas; se apenas as caixas mostradas estiverem disponíveis, então todas exceto a caixa verde.)

O problema da mochila é o seguinte problema de otimização combinatória:

Dado um conjunto de itens, cada um com um peso e um valor, determinar quais itens devem incluir na coleção de modo que o peso total é menor ou igual a um determinado limite e o valor total é tão grande quanto possível.

O nome deriva do problema enfrentado por alguém que é limitado por uma mochila de tamanho fixo e deve enchê-la com os itens mais valiosos. O problema geralmente surge na alocação de recursos, onde os tomadores de decisão precisam escolher entre um conjunto de projetos ou tarefas não divisíveis sob um orçamento fixo ou restrição de tempo, respectivamente.

O problema da mochila tem sido estudado por mais de um século, com os primeiros trabalhos datando de 1897. O nome "problema da mochila" remonta aos primeiros trabalhos do matemático Tobias Dantzig (1884-1956), e refere-se ao problema corriqueiro de empacotar os itens mais valiosos ou úteis sem sobrecarregar a bagagem.

Aplicativos

Os problemas da mochila aparecem em processos de tomada de decisão do mundo real em uma ampla variedade de campos, como encontrar a maneira menos dispendiosa de cortar matérias-primas, seleção de investimentos e portfólios, seleção de ativos para securitização lastreada em ativos e geração de chaves para o Merkle-Hellman e outros criptosistemas de mochila.

Uma das primeiras aplicações dos algoritmos de mochila foi na construção e pontuação de testes em que os examinandos podem escolher quais perguntas responder. Para pequenos exemplos, é um processo bastante simples fornecer essa escolha aos examinandos. Por exemplo, se um exame contém 12 questões cada uma valendo 10 pontos, o candidato precisa responder apenas 10 questões para atingir uma pontuação máxima possível de 100 pontos. No entanto, em testes com distribuição heterogênea de valores de pontos, é mais difícil fornecer escolhas. Feuerman e Weiss propuseram um sistema no qual os alunos recebem um teste heterogêneo com um total de 125 pontos possíveis. Os alunos são convidados a responder a todas as perguntas da melhor maneira possível. Dos possíveis subconjuntos de problemas cujos valores totais somam 100, um algoritmo de mochila determinaria qual subconjunto dá a cada aluno a pontuação mais alta possível.

Um estudo de 1999 do Stony Brook University Algorithm Repository mostrou que, de 75 problemas algorítmicos relacionados ao campo de algoritmos combinatórios e engenharia de algoritmos, o problema da mochila foi o 19º mais popular e o terceiro mais necessário após as árvores de sufixos e o problema de embalagem de lixo.

Definição

O problema mais comum que está sendo resolvido é o 0-1 knapsack problema, que restringe o número xEu...Não. x_{i}} de cópias de cada tipo de item a zero ou um. Dado um conjunto de nNão. itens numerados de 1 até nNão., cada um com um peso O quê?Eu...Não. w_{i}} e um valor vEu...Não. v_{i}}, juntamente com uma capacidade de peso máxima WNão. W.,

maximizar Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1nvEu...xEu...{displaystyle sum _{i=1}^{n}v_{i}x_{i}}

sujeito a Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1nO quê?Eu...xEu...≤ ≤ W{displaystyle sum _{i=1}^{n}w_{i}x_{i}leq W. e xEu...∈ ∈ (0,1?{displaystyle x_{i}in {0,1}}.

Aqui. xEu...Não. x_{i}} representa o número de instâncias do item Eu...Não. para incluir na mochila. Informalmente, o problema é maximizar a soma dos valores dos itens no knapsack para que a soma dos pesos seja inferior ou igual à capacidade do knapsack.

O problema de mochila limitada (BKP) remove a restrição de que há apenas um de cada item, mas restringe o número xEu...Não. x_{i}} de cópias de cada tipo de item a um valor inteiro máximo não negativo cNão.:

maximizar Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1nvEu...xEu...{displaystyle sum _{i=1}^{n}v_{i}x_{i}}

sujeito a Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1nO quê?Eu...xEu...≤ ≤ W{displaystyle sum _{i=1}^{n}w_{i}x_{i}leq W. e xEu...∈ ∈ (0,1,2,...... ,c?.{displaystyle x_{i}in}in {0,1,2,dotsc}.}

O unbounded knapsack problema (UKP) não coloca nenhum limite superior no número de cópias de cada tipo de item e pode ser formulado como acima, exceto que a única restrição xEu...Não. x_{i}} é que é um inteiro não negativo.

maximizar Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1nvEu...xEu...{displaystyle sum _{i=1}^{n}v_{i}x_{i}}

sujeito a Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1nO quê?Eu...xEu...≤ ≤ W{displaystyle sum _{i=1}^{n}w_{i}x_{i}leq W. e xEu...∈ ∈ Z.,xEu...≥ ≥ 0.{displaystyle x_{i}in mathbb {Z} x_{i}geq O quê?

Um exemplo do problema da mochila ilimitada é dado usando a figura mostrada no início deste artigo e o texto "se algum número de cada caixa estiver disponível" na legenda dessa figura.

Complexidade computacional

O problema da mochila é interessante do ponto de vista da ciência da computação por vários motivos:

• A forma de problema de decisão do problema do knapsack (Pode um valor de pelo menos V ser alcançado sem exceder o peso W?) é NP-completo, portanto, não há nenhum algoritmo conhecido que seja correto e rápido (polynomial-tempo) em todos os casos.
• Embora o problema da decisão seja NP-completo, o problema da otimização não é, sua resolução é pelo menos tão difícil quanto o problema da decisão, e não há um algoritmo polinomial conhecido que pode dizer, dada uma solução, se é ideal (o que significa que não há solução com um maior V, resolvendo assim o problema de decisão NP-completo).
• Há um algoritmo de tempo pseudo-polinomial usando programação dinâmica.
• Há um esquema de aproximação totalmente polinomial-tempo, que usa o algoritmo de tempo pseudo-polinomial como uma subrotina, descrito abaixo.
• Muitos casos que surgem na prática, e "casos aleatórios" de algumas distribuições, podem, no entanto, ser resolvidos exatamente.

Existe uma ligação entre a "decisão" e "otimização" problemas em que se existe um algoritmo polinomial que resolve a "decisão" problema, então pode-se encontrar o valor máximo para o problema de otimização em tempo polinomial aplicando este algoritmo iterativamente enquanto aumenta o valor de k. Por outro lado, se um algoritmo encontra o valor ótimo do problema de otimização em tempo polinomial, então o problema de decisão pode ser resolvido em tempo polinomial comparando o valor da solução produzida por esse algoritmo com o valor de k. Assim, ambas as versões do problema são de dificuldade semelhante.

Um tema na literatura de pesquisa é identificar o que o "difícil" As instâncias do problema da mochila parecem, ou vistas de outra maneira, para identificar quais propriedades das instâncias na prática podem torná-las mais receptivas do que sugere seu comportamento NP-completo de pior caso. O objetivo em encontrar esses itens "difíceis" instâncias é para seu uso em sistemas de criptografia de chave pública, como o criptosistema de mochila Merkle-Hellman.

Além disso, é notável o fato de que a dureza do problema da mochila depende da forma da entrada. Se os pesos e lucros forem dados como números inteiros, é fracamente NP-completo, enquanto é fortemente NP-completo se os pesos e lucros forem dados como números racionais. No entanto, no caso de pesos e lucros racionais, ele ainda admite um esquema de aproximação totalmente polinomial.

Resolvendo

Vários algoritmos estão disponíveis para resolver problemas da mochila, baseados na abordagem de programação dinâmica, na abordagem branch and bound ou hibridações de ambas as abordagens.

Algoritmo avançado de programação dinâmica

O unbounded knapsack problema (UKP) não restringe o número de cópias de cada tipo de item. Além disso, aqui vamos supor que 0}" xmlns="http://www.w3.org/1998/Math/MathML">xEu...>0{displaystyle x_{i}>0} 0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d7ca010976c6eb10a9e66a4ec495766452bfe828" style="vertical-align: -0.671ex; width:6.39ex; height:2.509ex;"/>

mNão.O quê??]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =máx.(Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1nvEu...xEu...){displaystyle m[w']=max left(sum _{i=1}^{n}v_{i}x_{i}right)}

sujeito a Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1nO quê?Eu...xEu...≤ ≤ O quê??{displaystyle sum _{i=1}^{n}w_{i}x_{i}leq O quê? e 0}" xmlns="http://www.w3.org/1998/Math/MathML">xEu...>0{displaystyle x_{i}>0} 0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d7ca010976c6eb10a9e66a4ec495766452bfe828" style="vertical-align: -0.671ex; width:6.39ex; height:2.509ex;"/>

Observe que mNão.O quê?]- Sim. tem as seguintes propriedades:

1. mNão.0]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0{displaystyle m[0]=0,!} (a soma de zero itens, ou seja, a soma do conjunto vazio).

2. mNão.O quê?]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =máx.(v1+mNão.O quê?- Sim. - Sim. O quê?1],v2+mNão.O quê?- Sim. - Sim. O quê?2],...,vn+mNão.O quê?- Sim. - Sim. O quê?n]){displaystyle m[w]=max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])}, O quê?Eu...≤ ≤ O quê?Não. w_{i}leq w}, onde vEu...Não. v_{i}} é o valor do Eu...Não.-o tipo de item.

A segunda propriedade precisa ser explicada em detalhes. Durante o processo de execução deste método, como obter o peso O quê?Não.? Só há Eu...Não. formas e os pesos anteriores são O quê?- Sim. - Sim. O quê?1,O quê?- Sim. - Sim. O quê?2,...,O quê?- Sim. - Sim. O quê?Eu...Não. w-w_{1},w-w_{2},...,w-w_{i}} onde há total Eu...Não. tipos de item diferente (por dizer diferente, queremos dizer que o peso e o valor não são completamente o mesmo). Se conhecermos cada valor destes Eu...Não. itens e o valor máximo relacionado anteriormente, nós apenas compará-los uns aos outros e obter o valor máximo em última análise e nós somos feitos.

Aqui o máximo do conjunto vazio é tomado para ser zero. Tabulando os resultados de mNão.0]- Sim. para cima mNão.W]- Sim. dá a solução. Desde o cálculo de cada mNão.O quê?]- Sim. envolve examinar no máximo nNão. itens, e há no máximo WNão. W. valores de mNão.O quê?]- Sim. para calcular, o tempo de execução da solução de programação dinâmica é O(nW)O(nW)}. Dividir O quê?1,O quê?2,...... ,O quê?n,WNão. w_{1},,w_{2},,ldots,w_{n},,W} por seu maior divisor comum é uma maneira de melhorar o tempo de execução.

Mesmo se P≠NP, o O(nW)O(nW)} complexidade não contradiz o fato de que o problema do knapsack é NP-completo, uma vez que WNão. W., ao contrário nNão., não é polinomial no comprimento da entrada para o problema. O comprimento do WNão. W. entrada para o problema é proporcional ao número de bits em WNão. W., log⁡ ⁡ W- Sim., não a WNão. W. em si. No entanto, uma vez que este tempo de execução é pseudopolynomial, isso faz com que a (versão de decisão do) problema knapsack um problema fracamente NP-completo.

Problema da mochila 0-1

Uma demonstração da abordagem dinâmica da programação.

Uma solução de programação dinâmica semelhante para o problema de knapsack 0-1 também é executado em tempo pseudo-polinomial. Assumir O quê?1,O quê?2,...... ,O quê?n,WNão. w_{1},,w_{2},,ldots,w_{n},,W} são inteiros estritamente positivos. Definir mNão.Eu...,O quê?]- Sim. para ser o valor máximo que pode ser alcançado com peso menor ou igual a O quê?Não. usando itens até Eu...Não. Primeiro Eu...Não. itens).

Podemos definir mNão.Eu...,O quê?]- Sim. recursivamente como segue: (Definição A)

• mNão.0,O quê?]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0[0,,w]=0}
• mNão.Eu...,O quê?]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =mNão.Eu...- Sim. - Sim. 1,O quê?][i,,w]=m[i-1,,w]} se w,!}" xmlns="http://www.w3.org/1998/Math/MathML">O quê?Eu...>O quê?Não. w_{i}>w,!}w,!" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9135ba545782f152ca4c833311af638b13cc6aee" style="vertical-align: -0.671ex; margin-right: -0.387ex; width:7.614ex; height:2.176ex;"/> (o novo item é mais do que o limite de peso atual)
• mNão.Eu...,O quê?]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =máx.(mNão.Eu...- Sim. - Sim. 1,O quê?],mNão.Eu...- Sim. - Sim. 1,O quê?- Sim. - Sim. O quê?Eu...]+vEu...)Não. m[i,,w]=max(m[i-1,,w],,m[i-1,w-w_{i}]+v_{i}) ? se O quê?Eu...⩽ ⩽ O quê?Não. w_{i}leqslant w}.

A solução pode então ser encontrada pelo cálculo mNão.n,W]- Sim.. Para fazer isso de forma eficiente, podemos usar uma tabela para armazenar cálculos anteriores.

O seguinte é pseudocódigo para o programa dinâmico:

// Entrada:// Valores (armazenados em array v)// Pesos (armazenados em array w)// Número de itens distintos (n)// Capacidade de Knapsack (W)// NOTA: O array "v" e array "w" são assumidos para armazenar todos os valores relevantes começando no índice 1.array mNão.0..n, 0..W]para JJ a partir de 0 para W do: mNão.0, JJ] ? 0para Eu... a partir de 1 para n do: mNão.Eu..., 0] ? 0para Eu... a partir de 1 para n do: para JJ a partir de 0 para W do: se O quê?Não.Eu...] > JJ então: mNão.Eu..., JJ] ? mNão.Eu...-1, JJ] mais: mNão.Eu..., JJ] ? máx.(mNão.Eu...-1, JJ] mNão.Eu...-1, JJ- Não.O quê?Não.Eu...] + vNão.Eu...]

Esta solução será, portanto, executada O(nW)O(nW)} tempo e O(nW)O(nW)} espaço. (Se só precisamos do valor m[n,W], podemos modificar o código de modo que a quantidade de memória necessária é O(W) que armazena as duas linhas recentes do array "m".)

No entanto, se dermos um passo ou dois mais, devemos saber que o método será executado no tempo entre O(nW)O(nW)} e O(2n)O(2^{n})}. A partir de Definição A, sabemos que não há necessidade de calcular todos os pesos quando o número de itens e os próprios itens que escolhemos são fixos. Ou seja, o programa acima computa mais do que necessário porque o peso muda de 0 para W muitas vezes. Nesta perspectiva, podemos programar este método para que ele seja executado recursivamente.

// Entrada:// Valores (armazenados em array v)// Pesos (armazenados em array w)// Número de itens distintos (n)// Capacidade de Knapsack (W)// NOTA: O array "v" e array "w" são assumidos para armazenar todos os valores relevantes começando no índice 1.Definir valorNão.n, W]Inicializar Todos valorNão.Eu..., JJ] = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = -1Definir m?(Eu...,JJ) // Defina a função m para que ele represente o valor máximo que podemos obter sob a condição: use primeiro i itens, limite de peso total é j( se Eu... - Sim. 0 ou JJ < 0 então: valorNão.Eu..., JJ] = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 0 retorno se (valorNão.Eu...-1, JJ] - Sim. -1) então: // m[i-1, j] não foi calculado, temos que chamar função m m(Eu...-1, JJ) se O quê?Não.Eu...] > JJ então: // item não pode caber no saco valorNão.Eu..., JJ] = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = valorNão.Eu...-1, JJ] mais:  se (valorNão.Eu...-1, JJ- Não.O quê?Não.Eu...] - Sim. -1) então: // m[i-1,j-w[i]] não foi calculado, temos que chamar função m m(Eu...-1, JJ- Não.O quê?Não.Eu...] valorNão.Eu..., JJ] = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = máx.(valorNão.Eu...-1,JJ] valorNão.Eu...-1, JJ- Não.O quê?Não.Eu...] + vNão.Eu...]?Corre! m(n, W)

Por exemplo, existem 10 itens diferentes e o limite de peso é 67. Portanto,

O quê?Não.1]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =23,O quê?Não.2]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =26,O quê?Não.3]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =20.,O quê?Não.4]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =18.,O quê?Não.5]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =32,O quê?Não.6]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =27,O quê?Não.7]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =29 de Março,O quê?Não.8]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =26,O quê?Não.9]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =30,O quê?Não.10.]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =27vNão.1]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =505,vNão.2]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =352,vNão.3]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =458,vNão.4]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =220 220,vNão.5]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =354,vNão.6]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =414,vNão.7]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =498,vNão.8]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =545,vNão.9]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =473,vNão.10.]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =543[8] [8]=26,w[3]=20,w[4]=18,w[5]=32,w[6]=27,w[7]=29,w[8]=26,w[9]=30,w[10]=27&v[1]=505,v[2]

m(10.,67)(10,67)}

m(Eu...,JJ)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0(i,j)=0}

m ( 10 , 67 ) = 1270 m ( 9 , 67 ) = 1270 , m ( 9 , 40 ) = 678 m ( 8 , 67 ) = 1270 , m ( 8 , 40 ) = 678 , m ( 8 , 37 ) = 545 m ( 7 , 67 ) = 1183 , m ( 7 , 41 ) = 725 , m ( 7 , 40 ) = 678 , m ( 7 , 37 ) = 505 m ( 6 , 67 ) = 1183 , m ( 6 , 41 ) = 725 , m ( 6 , 40 ) = 678 , m ( 6 , 38 ) = 678 , m ( 6 , 37 ) = 505 m ( 5 , 67 ) = 1183 , m ( 5 , 41 ) = 725 , m ( 5 , 40 ) = 678 , m ( 5 , 38 ) = 678 , m ( 5 , 37 ) = 505 m ( 4 , 67 ) = 1183 , m ( 4 , 41 ) = 725 , m ( 4 , 40 ) = 678 , m ( 4 , 38 ) = 678 , m ( 4 , 37 ) = 505 , m ( 4 , 35 ) = 505 m ( 3 , 67 ) = 963 , m ( 3 , 49 ) = 963 , m ( 3 , 41 ) = 505 , m ( 3 , 40 ) = 505 , m ( 3 , 38 ) = 505 , m ( 3 , 37 ) = 505 , m ( 3 , 35 ) = 505 , m ( 3 , 23 ) = 505 , m ( 3 , 22 ) = 458 , m ( 3 , 20 ) = 458 m ( 2 , 67 ) = 857 , m ( 2 , 49 ) = 857 , m ( 2 , 47 ) = 505 , m ( 2 , 41 ) = 505 , m ( 2 , 40 ) = 505 , m ( 2 , 38 ) = 505 , m ( 2 , 37 ) = 505 , m ( 2 , 35 ) = 505 , m ( 2 , 29 ) = 505 , m ( 2 , 23 ) = 505 m ( 1 , 67 ) = 505 , m ( 1 , 49 ) = 505 , m ( 1 , 47 ) = 505 , m ( 1 , 41 ) = 505 , m ( 1 , 40 ) = 505 , m ( 1 , 38 ) = 505 , m ( 1 , 37 ) = 505 , m ( 1 , 35 ) = 505 , m ( 1 , 29 ) = 505 , m ( 1 , 23 ) = 505 {displaystyle {begin{aligned}&m(10,67)=1270\&m(9,67)=1270,m(9,40)=678\&m(8,67)=1270,m(8,40)=678,m(8,37)=545\&m(7,67)=1183,m(7,41)=725,m(7,40)=678,m(7,37)=505\&m(6,67)=1183,m(6,41)=725,m(6,40)=678,m(6,38)=678,m(6,37)=505\&m(5,67)=1183,m(5,41)=725,m(5,40)=678,m(5,38)=678,m(5,37)=505\&m(4,67)=1183,m(4,41)=725,m(4,40)=678,m(4,38)=678,m(4,37)=505,m(4,35)=505\&m(3,67)=963,m(3,49)=963,m(3,41)=505,m(3,40)=505,m(3,38)=505,m(3,37)=505,m(3,35)=505,m(3,23)=505,m(3,22)=458,m(3,20)=458\&m(2,67)=857,m(2,49)=857,m(2,47)=505,m(2,41)=505,m(2,40)=505,m(2,38)=505,m(2,37)=505,m(2,35)=505,m(2,29)=505,m(2,23)=505\&m(1,67)=505,m(1,49)=505,m(1,47)=505,m(1,41)=505,m(1,40)=505,m(1,38)=505,m(1,37)=505,m(1,35)=505,m(1,29)=505,m(1,23)=505\end{aligned}}}

Além disso, podemos quebrar a recursão e convertê-la em uma árvore. Então podemos cortar algumas folhas e usar a computação paralela para agilizar a execução desse método.

Para encontrar o subconjunto real de itens, em vez de apenas seu valor total, podemos executar isso depois de executar a função acima:

Não. * Retorna os índices dos itens do knapsack ideal. * i: Podemos incluir itens 1 através de i no knapsack * j: peso máximo da mochila *função - Sim.(Eu...: - Não., JJ: - Não.): Conjunto<- Não.> ( se Eu... - Sim. 0 então: retorno Não. se mNão.Eu..., JJ] > mNão.Eu...-1, JJ] então: retorno (Eu...? Telecomunicações - Sim.(Eu...-1, JJ- Não.O quê?Não.Eu...] mais: retorno - Sim.(Eu...-1, JJ)?- Sim.(n, W)

Encontro no meio

Outro algoritmo para 0-1 knapsack, descoberto em 1974 e às vezes chamado de "meet-in-the-middle" devido a paralelos a um algoritmo similarmente chamado em criptografia, é exponencial no número de itens diferentes, mas pode ser preferível ao algoritmo DP quando WNão. W. é grande em comparação com n. Em particular, se o O quê?Eu...Não. w_{i}} são nonnegative, mas não inteiros, poderíamos ainda usar o algoritmo de programação dinâmica por escalonamento e arredondamento (ou seja, usando aritmética de ponto fixo), mas se o problema requer DNão. dígitos fracionários de precisão para chegar à resposta correta, WNão. W. terá de ser dimensionado por 10.D{displaystyle 10^{d}}, e o algoritmo DP vai exigir O(W10.D)(W10^{d})} espaço e O(nW10.D)(nW10^{d})} Hora.

algoritmo Meet-in-the-middle o entrada: Um conjunto de itens com pesos e valores.
 saída: O maior valor combinado de um subconjunto.

particionar o conjunto {1...nEm dois conjuntos A e B de aproximadamente tamanho igual
calcular os pesos e valores de todos os subconjuntos de cada conjunto

 para cada subconjunto de A doencontrar o subconjunto de B de maior valor tal que o peso combinado é menor do que Wmanter o controle do maior valor combinado visto até agora

O algoritmo leva O(2n/2)(2^{n/2})} espaço, e implementações eficientes da etapa 3 (por exemplo, classificar os subconjuntos de B em peso, descartar subconjuntos de B que pesam mais do que outros subconjuntos de B de maior ou igual valor, e usando busca binária para encontrar a melhor correspondência) resultam em um tempo de execução de O(n2n/2)(n2^{n/2})}. Como com o encontro no ataque médio em criptografia, isso melhora no O(n2n)(n2^{n})} tempo de execução de uma abordagem de força bruta ingênua (examinando todos os subconjuntos de (1...n?{displaystyle {1...n}}), ao custo de usar espaço exponencial em vez de constante (veja também a etapa gigante do bebê).

Algoritmos de aproximação

Como para a maioria dos problemas NP-completos, pode ser suficiente encontrar soluções viáveis, mesmo que não sejam ótimas. Preferencialmente, porém, a aproximação vem com a garantia da diferença entre o valor da solução encontrada e o valor da solução ótima.

Tal como acontece com muitos algoritmos úteis, mas computacionalmente complexos, tem havido pesquisas substanciais sobre a criação e análise de algoritmos que se aproximam de uma solução. O problema da mochila, embora NP-Difícil, é um de uma coleção de algoritmos que ainda podem ser aproximados em qualquer grau especificado. Isso significa que o problema possui um esquema de aproximação de tempo polinomial. Para ser exato, o problema da mochila tem um esquema de aproximação de tempo totalmente polinomial (FPTAS).

Algoritmo de aproximação gulosa

George Dantzig propôs um algoritmo de aproximação ganancioso para resolver o problema de knapsack não aderido. Sua versão classifica os itens em ordem decrescente de valor por unidade de peso, v1/O quê?1≥ ≥ ⋯ ⋯ ≥ ≥ vn/O quê?nNão. v_{1}/w_{1}geq cdots geq v_{n}/w_{n}}. Ele então prossegue para inseri-los no saco, começando com tantas cópias quanto possível do primeiro tipo de item até que não haja mais espaço no saco para mais. Desde que haja um fornecimento ilimitado de cada tipo de item, se mNão. é o valor máximo de itens que se encaixam no saco, então o algoritmo ganancioso é garantido para alcançar pelo menos um valor de m/2Não..

Para o problema limitado, onde o fornecimento de cada tipo de item é limitado, o algoritmo acima pode estar longe do ideal. No entanto, uma simples modificação nos permite resolver este caso: Assuma pela simplicidade que todos os itens se encaixam individualmente no saco (O quê?Eu...≤ ≤ WNão. w_{i}leq W. para todos Eu...Não.). Construir uma solução S1Não. S_{1}} embalando itens gananciosamente o maior tempo possível, i.e. S1= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(1,...... ,k?Não. S_{1}=left{1,ldotskright}} Onde? k= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =máx.1≤ ≤ k?≤ ≤ nGerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1k?O quê?Eu...≤ ≤ W{displaystyle k=textstyle max _{1leq k'leq n}textstyle sum _{i=1}^{k'}w_{i}leq W.. Além disso, construa uma segunda solução S2= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(k+1?Não. S_{2}=left{k+1right}} contendo o primeiro item que não se encaixava. Desde então S1Telecomunicações Telecomunicações S2{displaystyle S_{1}cup S_{2}} fornece um limite superior para o relaxamento LP do problema, um dos conjuntos deve ter valor pelo menos m/2Não.; nós, portanto, retornamos S1Não. S_{1}} e S2{displaystyle S_{2}} tem melhor valor para obter um 1/2- Sim.- aproximação.

Pode-se mostrar que o desempenho médio converge para a solução ideal na distribuição à taxa de erro n- Sim. - Sim. 1/2{displaystyle n^{-1/2}}

Esquema de aproximação de tempo totalmente polinomial

O esquema de aproximação de tempo totalmente polinomial (FPTAS) para o problema da mochila aproveita o fato de que o motivo pelo qual o problema não tem soluções de tempo polinomial conhecidas é porque os lucros associados aos itens não são restritos. Se alguém arredondar alguns dos dígitos menos significativos dos valores de lucro, eles serão limitados por um polinômio e 1/ε onde ε é um limite na exatidão da solução. Essa restrição significa que um algoritmo pode encontrar uma solução em tempo polinomial que seja correta dentro de um fator de (1-ε) da solução ótima.

algoritmo FPTAS o entrada: ε ∈ (0,1)
uma lista A de n itens, especificado por seus valores,      v  Eu...     Não. v_{i}} e pesos
 saída: S' a solução FPTAS

P:= máx.     (  v  Eu...   ∣ ∣  1 ≤ ≤  Eu... ≤ ≤  n ?   {displaystyle {v_{i}mid 1leq ileq n}}  // o valor mais alto do item
K:       P n     - Sim.  para Eu... a partir de 1 para n do      v  Eu...  ?    Não. v'_{i}} ?      ?    v  Eu...   KK   Gerenciamento de contas    {displaystyle leftlfloor} {displaystyle frac {v_{i}}{K}}rightrfloor }  fim para retorno a solução, S', usando      v  Eu...  ?    Não. v'_{i}}  valores no programa dinâmico descrito acima

Teorema: O conjunto S?Não. S'm computado pelo algoritmo acima satisfaz pRofEu...)(S?)≥ ≥ (1- Sim. - Sim. ε ε ))) pRofEu...)(S∗ ∗ )(S')geq (1-varepsilon)cdot mathrm {profit} (S^{*})}, onde S∗ ∗ Não. S^{*}} é uma solução ideal.

Relações de dominância

Resolver o problema do knapsack unbounded pode ser facilitado jogando fora itens que nunca serão necessários. Para um determinado item Eu...Não., supondo que poderíamos encontrar um conjunto de itens JJNão. tal que o seu peso total é menor do que o peso de Eu...Não., e seu valor total é maior do que o valor de Eu...Não.. Então... Eu...Não. não pode aparecer na solução ideal, porque sempre poderíamos melhorar qualquer solução potencial contendo Eu...Não. substituindo Eu...Não. com o conjunto JJNão.. Portanto, podemos ignorar o Eu...Não.-o item. Nestes casos, JJNão. é dito domina Eu...Não.. (Note que isso não se aplica a problemas de knapsack limitados, uma vez que podemos já ter usado até os itens em JJNão..)

Encontrar relações de dominância nos permite reduzir significativamente o tamanho do espaço de busca. Existem vários tipos diferentes de relações de dominância, que satisfazem uma desigualdade da forma:

Gerenciamento Gerenciamento JJ∈ ∈ JJO quê?JJxJJ≤ ≤ α α O quê?Eu...{displaystyle qquad sum _{jin J}w_{j},x_{j} leq alpha ,w_{i}}e Gerenciamento Gerenciamento JJ∈ ∈ JJvJJxJJ≥ ≥ α α vEu...{displaystyle sum _{jin J}v_{j},x_{j} geq alpha ,v_{i},} para alguns x∈ ∈ Z.+n{displaystyle xin Z_{+}^{n}}

Onde? α α ∈ ∈ Z.+,JJ⊊ ⊊ N{displaystyle alpha in Z_{+},,Jsubsetneq N} e Eu...∉JJ{displaystyle inot in J}. O vetor xNão. denota o número de cópias de cada membro de JJNão..

Collective dominance

The i {displaystyle i} -th item is collectively dominated by J {displaystyle J} , written as i ≪ J {displaystyle ill J} , if the total weight of some combination of items in J {displaystyle J} is less than w_i and their total value is greater than v_i. Formally, ∑ j ∈ J w j x j ≤ w i {displaystyle sum _{jin J}w_{j},x_{j} leq w_{i}} and ∑ j ∈ J v j x j ≥ v i {displaystyle sum _{jin J}v_{j},x_{j} geq v_{i}} for some x ∈ Z + n {displaystyle xin Z_{+}^{n}} , i.e. α = 1 {displaystyle alpha =1} . Verifying this dominance is computationally hard, so it can only be used with a dynamic programming approach. In fact, this is equivalent to solving a smaller knapsack decision problem where V = v i {displaystyle V=v_{i}} , W = w i {displaystyle W=w_{i}} , and the items are restricted to J {displaystyle J} .

Threshold dominance

The i {displaystyle i} -th item is threshold dominated by J {displaystyle J} , written as i ≺≺ J {displaystyle iprec prec J} , if some number of copies of i {displaystyle i} are dominated by J {displaystyle J} . Formally, ∑ j ∈ J w j x j ≤ α w i {displaystyle sum _{jin J}w_{j},x_{j} leq alpha ,w_{i}} , and ∑ j ∈ J v j x j ≥ α v i {displaystyle sum _{jin J}v_{j},x_{j} geq alpha ,v_{i},} for some x ∈ Z + n {displaystyle xin Z_{+}^{n}} and α ≥ 1 {displaystyle alpha geq 1} . This is a generalization of collective dominance, first introduced in and used in the EDUK algorithm. The smallest such α {displaystyle alpha } defines the threshold of the item i {displaystyle i} , written t i = ( α − 1 ) w i {displaystyle t_{i}=(alpha -1)w_{i}} . In this case, the optimal solution could contain at most α − 1 {displaystyle alpha -1} copies of i {displaystyle i} .

Multiple dominance

The i {displaystyle i} -th item is multiply dominated by a single item j {displaystyle j} , written as i ≪ m j {displaystyle ill _{m}j} , if i {displaystyle i} is dominated by some number of copies of j {displaystyle j} . Formally, w j x j ≤ w i {displaystyle w_{j},x_{j} leq w_{i}} , and v j x j ≥ v i {displaystyle v_{j},x_{j} geq v_{i}} for some x j ∈ Z + {displaystyle x_{j}in Z_{+}} i.e. J = { j } , α = 1 , x j = ⌊ w i w j ⌋ {displaystyle J={j},alpha =1,x_{j}=lfloor {frac {w_{i}}{w_{j}}}rfloor } . This dominance could be efficiently used during preprocessing because it can be detected relatively easily.

Modular dominance

Let b {displaystyle b} be the best item, i.e. v b w b ≥ v i w i {displaystyle {frac {v_{b}}{w_{b}}}geq {frac {v_{i}}{w_{i}}},} for all i {displaystyle i} . This is the item with the greatest density of value. The i {displaystyle i} -th item is modularly dominated by a single item j {displaystyle j} , written as i ≪ ≡ j {displaystyle ill _{equiv }j} , if i {displaystyle i} is dominated by j {displaystyle j} plus several copies of b {displaystyle b} . Formally, w j + t w b ≤ w i {displaystyle w_{j}+tw_{b}leq w_{i}} , and v j + t v b ≥ v i {displaystyle v_{j}+tv_{b}geq v_{i}} i.e. J = { b , j } , α = 1 , x b = t , x j = 1 {displaystyle J={b,j},alpha =1,x_{b}=t,x_{j}=1} .

Fossils of the Kellogg's beaver (Castor californicus) have been found in the US states of Washington, Oregon, Idaho, Nebraska, Kansas and California, and in the Mexican state of Sonora.

Introductions

In order to increase their numbers, specimens of Castor fiber have been released throughout Europe, especially in countries where they used to inhabit or continue to inhabit but their populations have decreased. For example, in October 2005, six European beavers were released in the county of Gloucestershire in Great Britain, and further reintroductions are planned in Scotland and Wales. In Spain, because their reintroduction took place clandestinely and without planning, was not fully welcomed by some, including the Ministry of the Environment of that nation. Its release in other countries, however, has been successful; an example of this are its introductions in Germany —specifically in Bavaria—, the Netherlands and Serbia. They have also returned to the banks of the Morava River, in Slovakia and the Czech Republic.

Essa variação altera o objetivo do indivíduo encher a mochila. Em vez de um objetivo, como maximizar o lucro monetário, o objetivo pode ter várias dimensões. Por exemplo, pode haver preocupações ambientais ou sociais, bem como objetivos econômicos. Os problemas frequentemente abordados incluem otimizações de portfólio e logística de transporte.

Por exemplo, suponha que você administre um navio de cruzeiro. Você tem que decidir quantos comediantes famosos contratar. Este barco não pode transportar mais de uma tonelada de passageiros e os animadores devem pesar menos de 1000 libras. Cada comediante tem um peso, faz negócios com base em sua popularidade e pede um salário específico. Neste exemplo, você tem vários objetivos. Você quer, é claro, maximizar a popularidade de seus artistas enquanto minimiza seus salários. Além disso, você deseja ter o maior número possível de artistas.

Problema da mochila multidimensional

Nesta variação, o peso do item de knapsack Eu...Não. é dado por um vetor D-dimensional O quê?Eu...? ? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(O quê?Eu...1,...... ,O quê?Eu...D)Não é verdade. {w_{i}}}=(w_{i1},ldotsw_{iD})} e o knapsack tem um vetor de capacidade D-dimensional (W1,...... ,WD)(W_{1},ldotsW_{D})}. O objetivo é maximizar a soma dos valores dos itens na mochila para que a soma de pesos em cada dimensão DNão. não exceda WDNão. W_{d}}.

O knapsack multidimensional é computacionalmente mais difícil do que o knapsack; mesmo para D= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =2Não., o problema não tem EPTAS a menos que P= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Não.NP. No entanto, o algoritmo em é mostrado para resolver instâncias esparsas de forma eficiente. Uma instância de mochila multidimensional é esparsa se houver um conjunto JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(1,2,...... ,m?Não. J={1,2,ldotsm}} para <math alttext="{displaystyle mm<DNão.<img alt="m tal que para cada item de mochila Eu...Não., m}" xmlns="http://www.w3.org/1998/Math/MathML">Detalhe Detalhe zangão.>m{displaystyle existe z>m}m" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ca38ed867e171d564a0cb209375f85274015a534" style="vertical-align: -0.338ex; width:7.52ex; height:2.176ex;"/> tal que Gerenciamento de contas Gerenciamento de contas JJ∈ ∈ JJTelecomunicações Telecomunicações (zangão.?,O quê?Eu...JJ≥ ≥ 0{displaystyle forall jin Jcup {z}, w_{ij}geq 0 e Gerenciamento de contas Gerenciamento de contas Sim.∉ ∉ JJTelecomunicações Telecomunicações (zangão.?,O quê?Eu...Sim.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0{displaystyle forall ynotin Jcup {z},w_{iy}=0}. Tais casos ocorrem, por exemplo, ao agendar pacotes em uma rede sem fio com nós de relé. O algoritmo também resolve instâncias esparsas da variante de múltipla escolha, mochila multidimensional de múltipla escolha.

O algoritmo IHS (Increasing Height Shelf) é ideal para mochila 2D (empacotamento de quadrados em um quadrado de tamanho de unidade bidimensional): quando há no máximo cinco quadrados em um empacotamento ideal.

Problema de várias mochilas

Esta variação é semelhante ao Problema de Empacotamento de Caixas. Ele difere do Problema de Empacotamento de Caixas porque um subconjunto de itens pode ser selecionado, enquanto que, no Problema de Embalagem de Caixas, todos os itens devem ser embalados em determinadas caixas. O conceito é que existem várias mochilas. Isso pode parecer uma mudança trivial, mas não equivale a aumentar a capacidade da mochila inicial. Essa variação é usada em muitos problemas de carregamento e escalonamento em Pesquisa Operacional e possui um esquema de aproximação de tempo polinomial.

Problema da mochila quadrática

O problema da mochila quadrática maximiza uma função objetivo quadrática sujeita a restrições de capacidade binárias e lineares. O problema foi introduzido por Gallo, Hammer e Simeone em 1980, no entanto, o primeiro tratamento do problema remonta a Witzgall em 1975.

Problema de soma de subconjuntos

O problema de soma subconjunto é um caso especial da decisão e 0-1 problemas onde cada tipo de item, o peso é igual ao valor: O quê?Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =vEu...Não. w_{i}=v_{i}}. No campo da criptografia, o termo problema de mochila é frequentemente usado para se referir especificamente ao problema de soma subconjunto e é comumente conhecido como um dos 21 problemas NP-completos de Karp.

A generalização do problema de soma de subconjuntos é chamada de problema de soma de subconjuntos múltiplos, em que existem vários compartimentos com a mesma capacidade. Foi demonstrado que a generalização não possui FPTAS.

Problema da mochila geométrica

No problema da mochila geométrica, existe um conjunto de retângulos com valores diferentes e uma mochila retangular. O objetivo é colocar o maior valor possível na mochila.