0/1 Correção de problema de mochila usando exemplo de programação dinâmica
Sarah Chen
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 irá levar para obter o maior valor?
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 levará embora.
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 fração 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 pela Estratégia Ganancioso.
Como resolver o problema da mochila usando programação dinâmica com exemplo
Na estratégia de dividir para conquistar, você divide o problema a ser resolvido em subproblemas. Os subproblemas são ainda divididos em subproblemas menores. Essa tarefa continuará até que você obtenha subproblemas que possam ser resolvidos facilmente. No entanto, no processo dessa divisão, você poderá encontrar o mesmo problema muitas vezes.
A ideia básica da programação dinâmica Knapsack é utilizar uma tabela para armazenar as soluções dos subproblemas resolvidos. Se você enfrentar um subproblema novamente, basta pegar a solução da tabela sem precisar resolvê-la novamente. Portanto, os algoritmos projetados por 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 programação dinâmica, você pode encontrar alguns pontos perceptíveis. O valor do algoritmo da mochila depende de dois fatores:
- Quantos pacotes estão sendo considerados
- 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:
- a função objetivo dependerá de duas quantidades variáveis
- a tabela de opções será uma tabela bidimensional.
Se chamar B[i][j] for 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 embalagens com limite de peso M é B[n][M]. Ou seja: Quando existem 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 dos pacotes selecionados é 8, quando há 4 primeiros pacotes para escolher (1º ao 4º pacote) e o peso máximo da mochila é 10. Não é necessário que todos os 4 itens estejam 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
![Fórmula para calcular B[i][j]](https://www.guru99.com/images/1/043019_0611_KnapsackPro4.png)
{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 que o peso máximo da mochila ≥ o peso do 1º pacote
B[1][j] = W[1]
Com o limite de peso j, as seleções ótimas entre os pacotes {1, 2, …, i – 1, i} para terem o maior valor terão duas possibilidades:
- Se o pacote i não for selecionado, B[i][j] é o valor máximo possível selecionando 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 este caso apenas 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 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 da Programação Dinâmica
Então, você tem que considerar se é melhor escolher o pacote i ou não. A partir daí você tem a fórmula recursiva da seguinte forma:
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 0 package = 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,
- Primeiramente, 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.
Traçar
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 limite de peso M.
- If B[n][M] = B[n – 1][M] então o pacote n não está selecionado, você rastreia B[n – 1][M].
- If B[n][M] ≠ B[n – 1][M], você percebe que a seleção ótima possui o pacote n e o traço B[n – 1][M – W[n]].
Continue traçando 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 está selecionado. B[n][W] é o valor total ideal do pacote colocado na mochila.
Etapas para rastreamento:
- 1º Passo: A partir de i = n, j = M.
- 2º Passo: Olhe na coluna j, de cima para baixo, você encontra a linha i tal que B[i][j] > B[i – 1][j]. Marcar pacote selecionado como i: Select [i] = true;
- 3º Passo: j = B[i][j] – W[i]. Se j > 0, vá para o passo 2, caso contrário, vá para o passo 4
- 4º Passo: Com base na tabela de opções para imprimir os pacotes selecionados.
Java Code
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 <= M; j++) {
B[i][j] = B[i - 1][j];
if ((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("\n");
}
System.out.println("Max Value:\t" + B[n][M]);
System.out.println("Selected Packs: ");
while (n != 0) {
if (B[n][M] != B[n - 1][M]) {
System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
M = M - W[n-1];
}
n--;
}
}
Explicação do código da mochila:
- Crie a tabela B[][]. Definir o valor padrão para cada célula é 0.
- Construa a tabela B[][] de baixo para cima. Calcule a tabela de opções com a fórmula de recuperação.
- Calcule B[i][j]. Se você não selecionar o pacote i.
- Em seguida, avalie: se você selecionar o pacote i, será mais benéfico do que redefinir B[i][j].
- Trace a tabela da linha n até a linha 0.
- Se você escolher o pacote n. Uma vez selecionado o pacote n, só é possível 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 a saída:
- 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
