The Knapsack problem
I found the Knapsack problem tricky and interesting at the same time. Tenho certeza de que se você estiver visitando esta página, você já sabe a declaração do problema, mas apenas por uma questão de realização :
Problema:
Dada uma Mochila de capacidade máxima de W e N itens, cada um com seu próprio valor e peso, jogar em itens dentro da Mochila de tal forma que o conteúdo final tem o valor máximo. Caramba !!,
Aqui está a forma geral como o problema é explicado – considere um ladrão entra em uma casa para roubar e ele carrega uma mochila. Há um número fixo de itens na casa – cada um com seu próprio peso e valor – jóias, com menos peso e mais alto valor vs tabelas, com menos valor, mas muito pesado. Para adicionar combustível ao fogo, O Ladrão tem uma mochila velha que tem capacidade limitada. Obviamente, ele não pode dividir a mesa em metade ou jóias em 3/4., Ele quer leva-lo ou deixa-lo
Exemplo :
Knapsack Max weight : W = 10 (units)Total items : N = 4Values of items : v = {10, 40, 30, 50}Weight of items : w = {5, 4, 6, 3}
Uma olhada superficial no exemplo dados nos diz que o valor máximo que podemos acomodar com o limite máximo de peso de 10 a 50 + 40 = 90, com um peso de 7.
Approach:
The way this is optimally solved is using dynamic programming – solving for smaller sets of knapsack problems and then expanding them for the bigger problem.,
let’s build an Item x Weight array called V (Value array):
V = 4 rows * 10 columnscada um dos valores desta matriz representa um problema menor do Knapsack.
base case 1: tomemos o caso da 0ª coluna. Significa apenas que a mochila tem 0 Capacidade. O que é que consegues segurar neles? Nada. Então, vamos enchê-los todos com 0s.
base case 2 : Vamos pegar o caso de 0 row. Significa apenas que não há itens na casa. O que você guarda na sua mochila se não houver itens. Nada outra vez !!! Todos os zeros.,
Solução:
1) Agora, vamos começar a preencher a matriz linha-sábio. O que significa a linha 1 e a coluna 1? Que dado o primeiro item( linha), você pode acomodá-lo na mochila com capacidade 1 (coluna). Nao. O peso do primeiro item é 5. Então, vamos preencher o 0. Na verdade, não seríamos capazes de preencher nada até chegarmos à coluna 5 (Peso 5).
2) Uma vez que chegamos à coluna 5 (que representa o peso 5) na primeira linha, significa que podemos acomodar o item 1., Vamos preencher 10 (lembre-se, este é um Valor de matriz):
3) de mudar, de peso 6 (coluna 6), podemos acomodar qualquer outra coisa com os restantes de peso de 1 (peso – o peso deste item => 6 – 5). Lembrem-se, estamos no primeiro item. Então, é meio intuitivo que o resto da linha será apenas o mesmo valor também, uma vez que somos incapazes de adicionar em qualquer outro item para esse peso extra que temos.,
4) assim, a próxima coisa interessante acontece quando chegamos à coluna 4 na terceira linha. O peso actual é de 4.
devemos verificar para os seguintes casos.
1) podemos acomodar o Item 2-Sim, podemos. O peso do Item 2 é 4.
2) o valor para o peso actual é maior sem o Item 2? – Verifique a linha anterior para o mesmo peso. Nao. a linha anterior * tem 0, uma vez que não fomos capazes de acomodar o Item 1 em peso 4.
3) podemos acomodar dois itens no mesmo peso para que possamos maximizar o valor? – Nao., O peso restante após dedução do Item2 é 0.
Por Que linha anterior?
simplesmente porque a linha anterior no weight 4 em si é uma solução menor knapsack que dá o valor máximo que poderia ser acumulado para esse peso até aquele ponto (atravessando os itens).,
Exemplificando,
1) O valor do item actual = 40
2) O peso do item atual = 4
3) O peso que está sobrando = 4 – 4 = 0
4) Verifique a linha acima (no Item acima, no caso do Item 1 ou cumulativa valor Máximo, no caso do restante das linhas). Para o restante Peso 0, podemos acomodar o Item 1? Simplificando, existe algum valor na linha acima para o peso dado?,
O cálculo vai assim :
1) Tomar o valor máximo para o mesmo peso, sem este item:
previous row, same weight = 0=> V2) Tomar o valor atual do item + valor que podemos acomodar com o restante do peso:
Max entre os dois é de 40 (0 e 40).
3) o evento seguinte e o mais importante acontece na coluna 9 e na linha 2. Significa que temos um peso de 9 e temos dois itens. Olhando para os dados de exemplo, poderíamos acomodar os dois primeiros itens., Aqui, vamos considerar algumas coisas:
- O valor do item actual = 40
- O peso do item atual = 4
- O peso que está sobrando = 9 – 4 = 5
- Verifique a linha acima. No peso restante 5, podemos acomodar o Item 1.
Assim, o cálculo é :
1) Tomar o valor máximo para o mesmo peso, sem este item:
previous row, same weight = 102) Tomar o valor atual do item + valor que poderíamos acumular com os restantes de peso:
Value of current item (40)+ value in previous row with weight 5 (total weight until now (9) - weight of the current item (4))= 1010 vs 50 = 50.,
No final de resolver todos esses problemas menores, só precisamos retornar o valor de V – Item 4, em Peso, 10:
Complexidade
Analisar a complexidade da solução é bem simples. Nós apenas temos um loop para W dentro de um loop de n=> O (NW)
implementação:
aqui vem o código de implementação obrigatório em Java: