Problema da mochila: Resolva usando exemplo de programação dinâmica

Qual é o problema da mochila?

Problema da mochila algoritmo é um problema muito útil em combinatória. No supermercado existem n embalagens (n ​​≤ 100) a embalagem i tem peso W [i] ≤ 100 e valor V [i] ≤ 100. Um ladrão invade o supermercado, o ladrão não pode carregar peso superior a M (M ≤ 100 ) O problema a ser resolvido aqui é: quais pacotes o ladrão vai tirar para conseguir o valor mais alto?

Entrada:

  • Peso máximo M e número de embalagens n.
  • Matriz de peso W [i] e valor correspondente V [i].

Saída:

  • Maximize o valor e o peso correspondente em capacidade.
  • Quais pacotes o ladrão vai tirar.

O algoritmo da mochila pode ser dividido em dois tipos:

  • O problema da mochila 0/1 usando programação dinâmica. Neste tipo de algoritmo de mochila, cada pacote pode ser levado ou não. Além disso, o ladrão não pode levar uma quantidade fracionária de um pacote levado ou levar um pacote mais de uma vez. Este tipo pode ser resolvido pela Abordagem de Programação Dinâmica.
  • Algoritmo do problema da mochila fracionária. Este tipo pode ser resolvido por Greedy Strategy.

Neste tutorial, você aprenderá:

Breve introdução à programação dinâmica

Na estratégia de dividir e conquistar, você divide o problema a ser resolvido em subproblemas. Os subproblemas são divididos em subproblemas menores. Essa tarefa continuará até que você obtenha subproblemas que possam ser resolvidos facilmente. No entanto, no processo de divisão, você pode encontrar o mesmo problema muitas vezes.

A ideia básica da programação dinâmica da mochila é usar uma tabela para armazenar as soluções dos subproblemas resolvidos. Se você enfrentar um subproblema novamente, basta pegar a solução da tabela sem ter que resolvê-la novamente. Portanto, os algoritmos projetados pela programação dinâmica são muito eficazes.

Para resolver um problema por programação dinâmica, você precisa realizar as seguintes tarefas:

  • Encontre soluções para os menores subproblemas.
  • Descubra a fórmula (ou regra) para construir uma solução de subproblema por meio de soluções até mesmo dos menores subproblemas.
  • Crie uma tabela que armazene as soluções dos subproblemas. Em seguida, calcule a solução do subproblema de acordo com a fórmula encontrada e salve na tabela.
  • A partir dos subproblemas resolvidos, você encontra a solução do problema original.

Analise o problema da mochila 0/1

Ao analisar o problema da mochila 0/1 usando a programação dinâmica, você pode encontrar alguns pontos perceptíveis. O valor do algoritmo da mochila depende de dois fatores:

  1. Quantos pacotes estão sendo considerados
  2. O peso restante que a mochila pode armazenar.

Portanto, você tem duas quantidades variáveis.

Com a programação dinâmica, você tem informações úteis:

  1. a função objetivo dependerá de duas quantidades variáveis
  2. a tabela de opções será uma tabela bidimensional.

Se chamar B [i] [j] é o valor máximo possível selecionando nos pacotes {1, 2, ..., i} com limite de peso j.

  • O valor máximo quando selecionado em n pacotes com o limite de peso M é B [n] [M]. Em outras palavras: quando há i embalagens para escolher, B [i] [j] é o peso ideal quando o peso máximo da mochila é j.
  • O peso ideal é sempre menor ou igual ao peso máximo: B [i] [j] ≤ j.

Por exemplo: B [4] [10] = 8. Significa que no caso ideal, o peso total das embalagens selecionadas é de 8, quando há 4 primeiras embalagens para escolher (1ª a 4ª embalagem) e o peso máximo da mochila é 10. Não é necessário que todos os 4 itens sejam selecionados.

Fórmula para calcular B [i] [j]

Entrada, você define:

  • W [i], V [i] são, por sua vez, o peso e o valor do pacote i, no qual i {1,…, n}.
  • M é o peso máximo que a mochila pode carregar.

No caso de simplesmente ter apenas 1 pacote para escolher. Você calcula B [1] [j] para cada j: o que significa o peso máximo da mochila ≥ o peso da 1ª embalagem

B[1][j] = W[1] 

Com o limite de peso j, as seleções ótimas entre os pacotes {1, 2, ..., i - 1, i} para ter o maior valor terão duas possibilidades:

  • Se o pacote i não for selecionado, B [i] [j] é o valor máximo possível ao selecionar entre os pacotes {1, 2, ..., i - 1} com limite de peso de j. Você tem:
B[i][j] = B[i – 1][j] 
  • Se o pacote i for selecionado (é claro, considere apenas este caso quando W [i] ≤ j) então B [i] [j] é igual ao valor V [i] do pacote i mais o valor máximo pode ser obtido selecionando-se entre embalagens {1, 2, ..., i - 1} com limite de peso (j - W [i]). Ou seja, em termos do valor que você tem:
B[i][j] = V[i] + B[i – 1][j – W[i]] 

Devido à criação de B [i] [j], que é o valor máximo possível, B [i] [j] será o máximo dos 2 valores acima.

Base de Programação Dinâmica

Portanto, você deve considerar se é melhor escolher o pacote i ou não. A partir daí, você tem a fórmula recursiva da seguinte maneira:

B[i][j]= max(B[i – 1][j], V[i]+B[i – 1][j – W[i]] 

É fácil ver B [0] [j] = valor máximo possível selecionando de 0 pacote = 0.

Calcule a Tabela de Opções

Você constrói uma tabela de opções com base na fórmula recursiva acima. Para verificar se os resultados estão corretos (se não exatamente, você reconstrói a função objetivo B [i] [j]). Através da criação da função objetivo B [i] [j] e da tabela de opções, você orientará o traçado.

A tabela de opções B inclui n + 1 linhas, M + 1 colunas,

  • Em primeiro lugar, preenchido com a base da programação dinâmica: a linha 0 inclui todos os zeros.
  • Usando fórmulas recursivas, use a linha 0 para calcular a linha 1, use a linha 1 para calcular a linha 2, etc. ... até que todas as linhas sejam calculadas.

Tabela de opções

Vestígio

Ao calcular a tabela de opções, você está interessado em B [n] [M] que é o valor máximo obtido ao selecionar em todos os n pacotes com o limite de peso M.

  • Se B [n] [M] = B [n - 1] [M] então o pacote n não é selecionado, você rastreia B [n - 1] [M].
  • Se B [n] [M] ≠ B [n - 1] [M] , você percebe que a seleção ótima tem o pacote ne o traço B [n - 1] [M - W [n]].

Continue a rastrear até chegar à linha 0 da tabela de opções.

Algoritmo para consultar a tabela de opções para encontrar os pacotes selecionados

Nota: Se B [i] [j] = B [i - 1] [j], o pacote i não é selecionado. B [n] [W] é o valor total ideal do pacote colocado na mochila.

Etapas para rastreamento:

  • Passo 1 : A partir de i = n, j = M.
  • Passo 2 : Olhe na coluna j, de cima para baixo, você encontra a linha i tal que B [i] [j]> B [i - 1] [j]. Marque o pacote selecionado i: Selecione [i] = verdadeiro;
  • etapa 3 : j = B [i] [j] - W [i]. Se j> 0, vá para a etapa 2, caso contrário, vá para a etapa 4
  • Passo 4 : Com base na tabela de opções para imprimir os pacotes selecionados.

Código Java

 public void knapsackDyProg(int W[], int V[], int M, int n) { int B[][] = new int[n + 1][M + 1]; for (int i=0; i<=n; i++) for (int j=0; j<=M; j++) { B[i][j] = 0; } for (int i = 1; i <= n; i++) { for (int j = 0; j = W[i-1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) { B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1]; } System.out.print(B[i][j] + ' '); } System.out.print('
'); } System.out.println('Max Value:	' + B[n][M]); System.out.println('Selected Packs: '); while (n != 0) { if (B[n][M] != B[n - 1][M]) { System.out.println('	Package ' + n + ' with W = ' + W[n - 1] + ' and Value = ' + V[n - 1]); M = M - W[n-1]; } n--; } } 

Função knapsackDyProg () em Java

Explicação do código da mochila:

  1. Crie a tabela B [] []. O valor padrão definido para cada célula é 0.
  2. Construa a tabela B [] [] de maneira ascendente. Calcule a tabela de opções com a fórmula de recuperação.
  3. Calcule B [i] [j]. Se você não selecionar o pacote i.
  4. Em seguida, avalie: se você selecionar o pacote i, será mais benéfico do que redefinir B [i] [j].
  5. Rastreie a tabela da linha n até a linha 0.
  6. Se você escolher o pacote n. Depois de selecionar o pacote n, só pode adicionar peso M - W [n - 1].

Neste tutorial, você tem dois exemplos. Aqui está o código java para executar o programa acima com dois exemplos:

 public void run() { /* * Pack and Weight - Value */ //int W[] = new int[]{3, 4, 5, 9, 4}; int W[] = new int[]{12, 2, 1, 1, 4}; //int V[] = new int[]{3, 4, 4, 10, 4}; int V[] = new int[]{4, 2, 1, 2, 10}; /* * Max Weight */ //int M = 11; int M = 15; int n = V.length; /* * Run the algorithm */ knapsackDyProg(W, V, M, n); } 

Você tem o resultado:

  • Primeiro exemplo:
 0 0 0 3 3 3 3 3 3 3 3 3 0 0 0 3 4 4 4 7 7 7 7 7 0 0 0 3 4 4 4 7 7 8 8 8 0 0 0 3 4 4 4 7 7 10 10 10 0 0 0 3 4 4 4 7 8 10 10 11 Max Value: 11 Selected Packs: Package 5 with W = 4 and Value = 4 Package 2 with W = 4 and Value = 4 Package 1 with W = 3 and Value = 3 
  • Segundo exemplo:
 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6 0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7 0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8 0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15 Max Value: 15 Selected Packs: Package 5 with W = 4 and Value = 10 Package 4 with W = 1 and Value = 2 Package 3 with W = 1 and Value = 1 Package 2 with W = 2 and Value = 2