Aqui a mochila é como um recipiente ou uma bolsa. Suponha que fornecemos alguns itens que têm algum peso ou lucro. Temos que colocar alguns itens na mochila de forma que o valor total produza o lucro máximo.

Por exemplo, o peso do contentor é de 20 kg. Temos que selecionar os itens de forma que a soma do peso dos itens seja menor ou igual ao peso do container, e o lucro seja máximo.

Existem dois tipos de problemas de mochila:

• 0/1 problema da mochila
• Problema da mochila fracionária

Discutiremos ambos os problemas um por um. Primeiro, aprenderemos sobre o problema da mochila 0/1.

Qual é o problema da mochila 0/1?

O problema da mochila 0/1 significa que os itens estão completamente ou nenhum item está preenchido em uma mochila. Por exemplo, temos dois itens com pesos de 2kg e 3kg, respectivamente. Se escolhermos o item de 2kg, não poderemos escolher o item de 1kg do item de 2kg (o item não é divisível); temos que escolher o item de 2kg completamente. Este é um problema de mochila 0/1 em que ou escolhemos o item completamente ou escolhemos esse item. O problema da mochila 0/1 é resolvido pela programação dinâmica.

Qual é o problema da mochila fracionária?

O problema da mochila fracionária significa que podemos dividir o item. Por exemplo, temos um item de 3kg então podemos pegar o item de 2kg e deixar o item de 1kg. O problema da mochila fracionária é resolvido pela abordagem Greedy.

Exemplo de problema da mochila 0/1.

Considere o problema em que os pesos e os lucros são:

Pesos: {3, 4, 6, 5}

Lucros: {2, 3, 1, 4}

O peso da mochila é de 8 kg

O número de itens é 4

O problema acima pode ser resolvido usando o seguinte método:

x_eu= {1, 0, 0, 1}

= {0, 0, 0, 1}

quais meses estão no terceiro trimestre

= {0, 1, 0, 1}

Acima estão as combinações possíveis. 1 indica que o item foi completamente separado e 0 significa que nenhum item foi separado. Como existem 4 itens, as combinações possíveis serão:

2⁴= 16; Então. Existem 16 combinações possíveis que podem ser feitas usando o problema acima. Uma vez feitas todas as combinações, temos que selecionar a combinação que proporciona o lucro máximo.

Outra abordagem para resolver o problema é a abordagem de programação dinâmica. Na abordagem de programação dinâmica, o problema complicado é dividido em subproblemas, então encontramos a solução de um subproblema e a solução do subproblema será usada para encontrar a solução de um problema complexo.

Como esse problema pode ser resolvido usando a abordagem de programação dinâmica?

Primeiro,

criamos uma matriz mostrada abaixo:

Na matriz acima, as colunas representam o peso, ou seja, 8. As linhas representam os lucros e os pesos dos itens. Aqui não pegamos o peso 8 diretamente, o problema é dividido em subproblemas, ou seja, 0, 1, 2, 3, 4, 5, 6, 7, 8. A solução dos subproblemas seria salva no células e a resposta ao problema seriam armazenadas na célula final. Primeiro, escrevemos os pesos em ordem crescente e os lucros de acordo com seus pesos mostrados abaixo:

Em_eu= {3, 4, 5, 6}

p_eu= {2, 3, 4, 1}

A primeira linha e a primeira coluna seriam 0, pois não há item para w = 0

Quando i=1, W=1

Em₁= 3; Como temos apenas um item no conjunto com peso 3, mas a capacidade da mochila é 1. Não podemos encher o item de 3kg na mochila com capacidade de 1 kg então adicione 0 em M[1][1] mostrado abaixo :

Quando eu = 1, W = 2

Em₁= 3; Como temos apenas um item no conjunto com peso 3, mas a capacidade da mochila é 2. Não podemos encher o item de 3kg na mochila com capacidade de 2 kg então adicione 0 em M[1][2] mostrado abaixo :

Quando i=1, W=3

Em₁= 3; Como temos apenas um item no conjunto com peso igual a 3, e o peso da mochila também é 3; portanto, podemos encher a mochila com um item de peso igual a 3. Colocamos o lucro correspondente ao peso 3, ou seja, 2 em M[1][3] mostrado abaixo:

Quando i = 1, W = 4

_W1= 3; Como temos apenas um item no conjunto com peso igual a 3, e o peso da mochila é 4; portanto, podemos encher a mochila com um item de peso igual a 3. Colocamos o lucro correspondente ao peso 3, ou seja, 2 em M[1][4] mostrado abaixo:

Quando i = 1, W = 5

_W1= 3; Como temos apenas um item no conjunto com peso igual a 3, e o peso da mochila é 5; portanto, podemos encher a mochila com um item de peso igual a 3. Colocamos o lucro correspondente ao peso 3, ou seja, 2 em M[1][5] mostrado abaixo:

Quando eu =1, W=6

_W1= 3; Como temos apenas um item no conjunto com peso igual a 3, e o peso da mochila é 6; portanto, podemos encher a mochila com um item de peso igual a 3. Colocamos o lucro correspondente ao peso 3, ou seja, 2 em M[1][6] mostrado abaixo:

Quando i = 1, W = 7

_W1= 3; Como temos apenas um item no conjunto com peso igual a 3, e o peso da mochila é 7; portanto, podemos encher a mochila com um item de peso igual a 3. Colocamos o lucro correspondente ao peso 3, ou seja, 2 em M[1][7] mostrado abaixo:

Quando eu =1, W =8

_W1= 3; Como temos apenas um item no conjunto com peso igual a 3, e o peso da mochila é 8; portanto, podemos encher a mochila com um item de peso igual a 3. Colocamos o lucro correspondente ao peso 3, ou seja, 2 em M[1][8] mostrado abaixo:

Agora o valor de 'i' é incrementado e se torna 2.

Quando eu = 2, W = 1

O peso correspondente ao valor 2 é 4, ou seja, w₂= 4. Como temos apenas um item no conjunto com peso igual a 4, e o peso da mochila é 1. Não podemos colocar o item de peso 4 em uma mochila, então somamos 0 em M[2][1 ] mostrado abaixo:

Quando eu = 2, W = 2

O peso correspondente ao valor 2 é 4, ou seja, w₂= 4. Como temos apenas um item no conjunto com peso igual a 4, e o peso da mochila é 2. Não podemos colocar o item de peso 4 em uma mochila, então somamos 0 em M[2][2 ] mostrado abaixo:

Quando eu = 2, W = 3

O peso correspondente ao valor 2 é 4, ou seja, w₂= 4. Como temos dois itens no conjunto com pesos 3 e 4, e o peso da mochila é 3. Podemos colocar o item de peso 3 em uma mochila, então somamos 2 em M[2][3] mostrado abaixo:

Quando eu = 2, W = 4

O peso correspondente ao valor 2 é 4, ou seja, w₂= 4. Como temos dois itens no conjunto com pesos 3 e 4, e o peso da mochila é 4. Podemos colocar o item de peso 4 em uma mochila, pois o lucro correspondente ao peso 4 é maior que o item com peso 3, então adicionamos 3 em M[2][4] mostrado abaixo:

Quando eu = 2, W = 5

O peso correspondente ao valor 2 é 4, ou seja, w₂= 4. Como temos dois itens no conjunto com pesos 3 e 4, e o peso da mochila é 5. Podemos colocar um item de peso 4 em uma mochila e o lucro correspondente ao peso é 3, então somamos 3 em M[2][5] mostrado abaixo:

Quando eu = 2, W = 6

O peso correspondente ao valor 2 é 4, ou seja, w₂= 4. Como temos dois itens no conjunto com pesos 3 e 4, e o peso da mochila é 6. Podemos colocar um item de peso 4 em uma mochila e o lucro correspondente ao peso é 3, então somamos 3 em M[2][6] mostrado abaixo:

Quando eu = 2, W = 7

O peso correspondente ao valor 2 é 4, ou seja, w₂= 4. Como temos dois itens no conjunto com pesos 3 e 4, e o peso da mochila é 7. Podemos colocar itens de peso 4 e 3 em uma mochila e os lucros correspondentes aos pesos são 2 e 3; portanto, o lucro total é 5, então adicionamos 5 em M[2][7] mostrado abaixo:

Quando eu = 2, W = 8

O peso correspondente ao valor 2 é 4, ou seja, w₂= 4. Como temos dois itens no conjunto com pesos 3 e 4, e o peso da mochila é 7. Podemos colocar itens de peso 4 e 3 em uma mochila e os lucros correspondentes aos pesos são 2 e 3; portanto, o lucro total é 5, então adicionamos 5 em M[2][7] mostrado abaixo:

Agora o valor de 'i' é incrementado e se torna 3.

Quando eu = 3, W = 1

finalizar a compra com git

O peso correspondente ao valor 3 é 5, ou seja, w₃= 5. Como temos três itens no conjunto com pesos 3, 4 e 5, e o peso da mochila é 1. Não podemos colocar nenhum dos itens em uma mochila, então adicionamos 0 em M[3][ 1] mostrado abaixo:

Quando eu = 3, W = 2

O peso correspondente ao valor 3 é 5, ou seja, w₃= 5. Como temos três itens no conjunto com peso 3, 4 e 5, e o peso da mochila é 1. Não podemos colocar nenhum dos itens em uma mochila, então adicionamos 0 em M[3][ 2] mostrado abaixo:

Quando eu = 3, W = 3

O peso correspondente ao valor 3 é 5, ou seja, w₃= 5. Como temos três itens no conjunto com peso 3, 4 e 5 respectivamente e o peso da mochila é 3. O item com peso 3 pode ser colocado na mochila e o lucro correspondente ao item é 2, então adicionamos 2 em M[3][3] mostrado abaixo:

Quando eu = 3, W = 4

O peso correspondente ao valor 3 é 5, ou seja, w₃= 5. Como temos três itens no conjunto com peso 3, 4 e 5 respectivamente, e o peso da mochila é 4. Podemos ficar com o item com peso 3 ou 4; o lucro (3) correspondente ao peso 4 é maior que o lucro correspondente ao peso 3, então adicionamos 3 em M[3][4] mostrado abaixo:

Quando eu = 3, W = 5

O peso correspondente ao valor 3 é 5, ou seja, w₃= 5. Como temos três itens no conjunto com peso 3, 4 e 5 respectivamente, e o peso da mochila é 5. Podemos manter o item com peso 3, 4 ou 5; o lucro (3) correspondente ao peso 4 é maior que os lucros correspondentes ao peso 3 e 5, então adicionamos 3 em M[3][5] mostrado abaixo:

numerando o alfabeto

Quando eu =3, W = 6

O peso correspondente ao valor 3 é 5, ou seja, w₃= 5. Como temos três itens no conjunto com peso 3, 4 e 5 respectivamente, e o peso da mochila é 6. Podemos manter o item com peso 3, 4 ou 5; o lucro (3) correspondente ao peso 4 é maior que os lucros correspondentes ao peso 3 e 5, então adicionamos 3 em M[3][6] mostrado abaixo:

Quando eu =3, W = 7

O peso correspondente ao valor 3 é 5, ou seja, w₃= 5. Como temos três itens no conjunto de peso 3, 4 e 5 respectivamente, e o peso da mochila é 7. Nesse caso, podemos manter ambos os itens de peso 3 e 4, a soma do lucro seria igual a (2 + 3), ou seja, 5, então adicionamos 5 em M[3][7] mostrado abaixo:

Quando eu = 3, W = 8

O peso correspondente ao valor 3 é 5, ou seja, w₃= 5. Como temos três itens no conjunto de peso 3, 4 e 5 respectivamente, e o peso da mochila é 8. Nesse caso, podemos manter ambos os itens de peso 3 e 4, a soma dos o lucro seria igual a (2 + 3), ou seja, 5, então adicionamos 5 em M[3][8] mostrado abaixo:

Agora o valor de 'i' é incrementado e se torna 4.

Quando eu = 4, W = 1

O peso correspondente ao valor 4 é 6, ou seja, w₄= 6. Como temos quatro itens no conjunto de pesos 3, 4, 5 e 6 respectivamente, e o peso da mochila é 1. O peso de todos os itens é maior que o peso da mochila, então não podemos adicione qualquer item na mochila; Portanto, adicionamos 0 em M[4][1] mostrado abaixo:

Quando eu = 4, W = 2

O peso correspondente ao valor 4 é 6, ou seja, w₄= 6. Como temos quatro itens no conjunto de pesos 3, 4, 5 e 6 respectivamente, e o peso da mochila é 2. O peso de todos os itens é maior que o peso da mochila, então não podemos adicione qualquer item na mochila; Portanto, adicionamos 0 em M[4][2] mostrado abaixo:

Quando eu = 4, W = 3

O peso correspondente ao valor 4 é 6, ou seja, w₄= 6. Como temos quatro itens no conjunto de pesos 3, 4, 5 e 6 respectivamente, e o peso da mochila é 3. O item com peso 3 pode ser colocado na mochila e o lucro correspondente ao o peso 4 é 2, então adicionaremos 2 em M[4][3] mostrado abaixo:

Quando eu = 4, W = 4

O peso correspondente ao valor 4 é 6, ou seja, w₄= 6. Como temos quatro itens no conjunto de pesos 3, 4, 5 e 6 respectivamente, e o peso da mochila é 4. O item com peso 4 pode ser colocado na mochila e o lucro correspondente ao o peso 4 é 3, então adicionaremos 3 em M[4][4] mostrado abaixo:

Quando eu = 4, W = 5

O peso correspondente ao valor 4 é 6, ou seja, w₄= 6. Como temos quatro itens no conjunto de pesos 3, 4, 5 e 6 respectivamente, e o peso da mochila é 5. O item com peso 4 pode ser colocado na mochila e o lucro correspondente ao o peso 4 é 3, então adicionaremos 3 em M[4][5] mostrado abaixo:

Quando eu = 4, W = 6

O peso correspondente ao valor 4 é 6, ou seja, w₄= 6. Como temos quatro itens no conjunto com pesos 3, 4, 5 e 6 respectivamente, e o peso da mochila é 6. Nesse caso, podemos colocar os itens na mochila com peso 3, 4 , 5 ou 6 mas o lucro, ou seja, 4 correspondente ao peso 6 é o maior entre todos os itens; portanto, adicionamos 4 em M[4][6] mostrado abaixo:

Quando eu = 4, W = 7

O peso correspondente ao valor 4 é 6, ou seja, w₄= 6. Como temos quatro itens no conjunto de pesos 3, 4, 5 e 6 respectivamente, e o peso da mochila é 7. Aqui, se somarmos dois itens de pesos 3 e 4 então produzirá o máximo lucro, ou seja, (2 + 3) é igual a 5, então adicionamos 5 em M[4][7] mostrado abaixo:

Quando eu = 4, W = 8

O peso correspondente ao valor 4 é 6, ou seja, w₄= 6. Como temos quatro itens no conjunto de pesos 3, 4, 5 e 6 respectivamente, e o peso da mochila é 8. Aqui, se somarmos dois itens de pesos 3 e 4 então produzirá o máximo lucro, ou seja, (2 + 3) é igual a 5, então adicionamos 5 em M[4][8] mostrado abaixo:

Como podemos observar na tabela acima que 5 é o lucro máximo entre todas as entradas. O ponteiro aponta para a última linha e a última coluna com valor 5. Agora vamos comparar o valor 5 com a linha anterior; se a linha anterior, ou seja, i = 3 contiver o mesmo valor 5, o ponteiro se deslocará para cima. Como a linha anterior contém o valor 5, o ponteiro será deslocado para cima, conforme mostrado na tabela abaixo:

Novamente, compararemos o valor 5 da linha acima, ou seja, i = 2. Como a linha acima contém o valor 5, o ponteiro será novamente deslocado para cima, conforme mostrado na tabela abaixo:

Novamente, compararemos o valor 5 da linha acima, ou seja, i = 1. Como a linha acima não contém o mesmo valor, consideraremos a linha i=1, e o peso correspondente à linha é 4. Portanto , selecionamos o peso 4 e rejeitamos os pesos 5 e 6 mostrados abaixo:

x = {1, 0, 0}

O lucro correspondente ao peso é 3. Portanto, o lucro restante é (5 - 3) igual a 2. Agora vamos comparar este valor 2 com a linha i = 2. Como a linha (i = 1) contém o valor 2 ; portanto, o ponteiro deslocou-se para cima mostrado abaixo:

Novamente comparamos o valor 2 com uma linha acima, ou seja, i = 1. Como a linha i = 0 não contém o valor 2, então a linha i = 1 será selecionada e o peso correspondente a i = 1 é 3 mostrado abaixo:

X = {1, 1, 0, 0}

O lucro correspondente ao peso é 2. Portanto, o lucro restante é 0. Comparamos o valor 0 com a linha acima. Como a linha acima contém um valor 0, mas o lucro correspondente a esta linha é 0. Neste problema, dois pesos são selecionados, ou seja, 3 e 4 para maximizar o lucro.