Atualização: Leia sobre como otimizar o espaço complexidade da dinâmica de solução de programação em meu artigo follow-up aqui.,
A Mochila Problema é realmente um problema interessante em combinatória — para citar a Wikipédia,
“dado um conjunto de itens, cada um com um peso e um valor, determinar o número de cada item para incluir em uma coleção, de modo que o peso total seja menor ou igual a um determinado limite e o valor total é de tão grande quanto possível.”
da Wikipédia, vemos que existem algumas variações do problema da mochila: 0-1 knapsack, knapsack limitado, e knapsack ilimitado., Hoje, vamos nos concentrar na variação mais comum (e mais simples): o problema da mochila 0-1.
uma fraseologia ligeiramente mais interessante e relacionável do problema da mochila 0-1 é:
considere que um ladrão entra numa casa para roubar e ele carrega uma mochila. Há 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. É pegar ou largar. Fonte
infelizmente, tive alguma dificuldade em compreender algumas partes do artigo Hackerearth, razão pela qual decidi escrever o meu próprio artigo. Este artigo será em grande parte baseado no artigo do Hackerearth e os excertos de código são escritos em Java. Vou trabalhar em explicações adicionais e elaborações onde as sinto necessárias.vamos resolver este problema com programação dinâmica., A programação dinâmica requer uma subestrutura óptima e sub-problemas sobrepostos, ambos presentes no problema da mochila 0-1, como veremos.
é bom se você não entende o que são “subestrutura ótima” e “sub-problemas sobrepostos” (que é um artigo para outro dia). Essencialmente, significa apenas um sabor particular de problemas, que nos permitem reutilizar anterior soluções para problemas menores, a fim de calcular uma solução para o problema atual. Vais ver o que quero dizer daqui a pouco.,
detalhes do problema
Uma vez que este é o problema da mochila 0-1, podemos incluir um item na nossa mochila ou excluí-lo, mas não incluir uma fração dele, ou incluí-lo várias vezes.
Solução
Primeiro, criamos um 2-vetor (por exemplo, uma tabela) de n + 1 linhas e w + 1 colunas.
um número de linha I representa o conjunto de todos os itens das linhas 1— i. por exemplo, os valores na linha 3 assume que só temos itens 1, 2 e 3.
um número de coluna j representa a capacidade de peso da nossa mochila., Portanto, os valores na coluna 5, por exemplo, assumem que a nossa mochila pode conter 5 unidades de peso.
Juntando tudo, uma entrada na linha i, coluna j representa o valor máximo que pode ser obtido com itens 1, 2, 3 … i, em uma mochila que pode conter unidades de peso J.
vamos chamar a nossa tabela mat para matrix. Portanto, int mat = new int.
Passo 2:
podemos começar imediatamente a preencher algumas entradas na nossa tabela: os casos base, para os quais a solução é trivial., Por exemplo, na linha 0, quando não temos itens para escolher, o valor máximo que pode ser armazenado em qualquer mochila deve ser 0. Da mesma forma, na coluna 0, para uma mochila que pode conter 0 unidades de peso, o valor máximo que pode ser armazenado nela é 0. (Presumimos que não há itens sem massa e valiosos.)
Nós podemos fazer isso com 2 ciclos:
Passo 3 (o x do problema):
Agora, queremos começar a preencher a nossa tabela., Tal como acontece com todas as soluções de programação dinâmica, a cada passo, utilizaremos as nossas soluções para os sub-problemas anteriores.
vou primeiro descrever a lógica, antes de mostrar um exemplo concreto.
A relação entre o valor na linha i, coluna j e os valores para os sub-problemas anteriores é a seguinte:
lembre-se que na linha i e coluna j, estamos enfrentando um sub-problema consistindo de itens 1, 2, 3 … I com uma mochila de capacidade j. Existem duas opções neste ponto: podemos incluir o item i ou não., Portanto, nós precisamos comparar o valor máximo que podemos obter com e sem item i.
O valor máximo que podemos obter, sem item que pode ser encontrado na linha i-1, coluna j. Essa parte é fácil. O raciocínio é simples: qualquer que seja o valor máximo que podemos obter com os itens 1, 2, 3 … eu deve, obviamente, ser o mesmo valor máximo que podemos obter com os itens 1, 2, 3 … i – 1, se optar por não incluir o item i.
Para calcular o valor máximo que podemos obter com o item i, primeiro precisamos comparar o peso do item i, com a mochila sobre a capacidade de peso., Obviamente, se o item eu pesa mais do que o que a mochila pode segurar, não podemos incluí-lo, então não faz sentido realizar o cálculo. Nesse caso, a solução para este problema é simplesmente o valor máximo que podemos obter sem o item i (ou seja, o valor na linha acima, na mesma coluna).
no entanto, suponha que o item I pesa menos do que a capacidade da mochila. Assim, temos a opção de incluí-lo, se ele potencialmente aumentar o valor máximo alcançável., O valor máximo que pode ser obtido ao incluir o item i é assim = o valor do próprio item I + O valor máximo que pode ser obtido com a capacidade restante da mochila. Queremos, obviamente, fazer pleno uso da capacidade da nossa mochila e não deixar que nenhuma capacidade restante vá para o lixo.
Portanto, na linha i e coluna j (que representa o valor máximo que podemos obter lá), que iria pegar o máximo de valor que podemos obter sem o item i, ou o valor máximo que podemos obter com o item i, o que for maior.aqui está um exemplo concreto do que quero dizer.,
linha 3 (item 2), e a coluna 5 (mochila de capacidade de 4), pode-se optar por incluir o item 2 (que pesa 4 unidades) ou não. Se optarmos por não incluí-lo, o valor máximo que podemos obter é o mesmo que se tivermos apenas o item 1 para escolher (que é encontrado na linha acima, ou seja, 0)., Se queremos incluir o item 2, o valor máximo que podemos obter com o item 2 é o valor do número 2 (40) + o valor máximo que podemos obter com a capacidade restante (que é 0, porque a mochila é completamente cheia, já).
na linha 3( item 2), e coluna 10 (Capacidade da mochila de 9), novamente, podemos optar por incluir o item 2 ou não. Se optarmos por não o fazer, o valor máximo que podemos obter é o mesmo que na linha acima na mesma coluna, ou seja, 10 (incluindo apenas o item 1, que tem um valor de 10). Se incluirmos o item 2, temos uma capacidade de Mochila restante de 9-4 = 5., Podemos descobrir o valor máximo que pode ser obtido com uma capacidade de 5 olhando para a linha acima, na coluna 5. Assim, o valor máximo que podemos obter ao incluir o item 2 é 40 (o valor do item 2) + 10 = 50.
Nós escolhemos o maior de 50 vs 10, e assim o valor máximo que podemos obter com itens 1 e 2, com uma capacidade de Mochila de 9, é 50.,
O algoritmo pode ser expresso em Java como este:
Passo 4 (solução final):
uma Vez que a tabela foi preenchida, a solução final pode ser encontrado na última linha da última coluna, o que representa o valor máximo obtido com todos os itens e o total da capacidade da mochila.
return mat;
código de trabalho:
nota: aqui, eu imprimi a resposta final em vez de devolvê-la, uma vez que tudo está alojado sob público vazio estático principal.,
Thanks for reading!