0/1 Correção de problema de mochila usando exemplo de programação dinâmica

Qual é o problema da mochila?

O Problema da mochila é um problema clássico de otimização combinatória. Um supermercado armazena n pacotes (n ≤ 100). Pacote i Um ladrão possui um pacote com peso W[i] ≤ 100 e valor V[i] ≤ 100. Ele não pode carregar um peso superior à capacidade M (M ≤ 100). Quais pacotes o ladrão deve levar para maximizar o valor total?

Entrada:

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

Saída:

• Valor total máximo que pode ser obtido dentro da capacidade.
• O conjunto exato de encomendas que o ladrão deve levar.

O algoritmo da mochila se divide em duas variantes bem conhecidas:

• Problema da Mochila 0/1 Resolvido por Programação Dinâmica. Cada pacote é considerado inteiro ou descartado — sem partes fracionárias e sem duplicatas.
• Problema da mochila fracionária resolvido por uma estratégia gulosa. Aqui você pode pegar uma fração de qualquer pacote para preencher a capacidade restante.

Como resolver o problema da mochila usando programação dinâmica com exemplo

A estratégia de dividir para conquistar divide um grande problema em subproblemas e continua dividindo até que cada subproblema se torne fácil. A recursão simples, por outro lado, muitas vezes resolve o mesmo subproblema diversas vezes, desperdiçando trabalho.

A ideia central da Programação Dinâmica com Mochila é armazenar cada subproblema resolvido em uma tabela. Chamadas repetidas leem a resposta em vez de recalculá-la, transformando uma recursão exponencial em código de tempo polinomial.

Resolva o problema da mochila usando programação dinâmica

Para projetar uma solução de Programação Dinâmica, você segue quatro etapas:

• Resolva primeiro os subproblemas menores.
• Deduza uma recorrência que construa a resposta de um subproblema a partir de respostas de subproblemas menores.
• Armazene as respostas dos subproblemas em uma tabela calculada de baixo para cima usando a recorrência.
• Monte a resposta final a partir da tabela totalmente preenchida.

Analise o problema da mochila 0/1

O valor ideal depende de dois fatores independentes:

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

Como a função objetivo depende de duas quantidades, a tabela de opções deve ser bidimensional. Seja B[i][j] denota o valor máximo ao escolher entre pacotes {1, …, i} com limite de peso j.

• A resposta final é B[n][M], o melhor valor total entre todos os n pacotes com capacidade M.
• O peso total selecionado é sempre limitado pela capacidade atual: B[i][j] ≤ j.

Exemplo: se B[4][10] = 8, o melhor peso total dos primeiros quatro pacotes com capacidade inferior a 10 é 8. Alguns desses quatro pacotes podem ser ignorados.

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

• W[i], V[i] são o peso e o valor do pacote i, onde i está em {1, …, n}.
• M é o peso máximo que a mochila pode carregar.

Caso base com um pacote: para cada capacidade j ≥ W[1]:

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

Para o caso geral, decida se o pacote i deve ser incluído na capacidade j:

• Se o pacote i for ignorado, B[i][j] é igual ao melhor valor usando pacotes {1, …, i-1} com capacidade j:

B[i][j] = B[i - 1][j]

• Se o pacote i for tomado (permitido apenas quando W[i] ≤ j), B[i][j] é igual a V[i] mais o melhor valor dos pacotes {1, …, i-1} com capacidade j – W[i]:

B[i][j] = V[i] + B[i - 1][j - W[i]]

Escolha o maior dos dois candidatos.

Base da Programação Dinâmica

A combinação dos dois casos resulta na recorrência completa:

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

O caso base é B[0][j] = 0 para cada j, porque zero pacotes não geram valor algum, independentemente da capacidade.

Calcule a tabela de opções

Construa B usando a recorrência. Assim que B estiver preenchido, a mesma tabela controla o próximo passo. trace-back que reconstrói os pacotes escolhidos. A tabela B tem n + 1 linhas e M + 1 colunas:

• A linha 0 representa o caso base, preenchida com zeros.
• Use a linha 0 para calcular a linha 1, a linha 1 para calcular a linha 2 e continue até que a linha n esteja completa.

Tabela de Opções

Trace

Assim que B estiver concluído, concentre-se em B[n][M], o valor total ideal em todos os n pacotes com capacidade M.

• If B[n][M] = B[n-1][M]O pacote n não foi selecionado, então continue. tracde B[n-1][M].
• If B[n][M] ≠ B[n-1][M]O pacote n foi selecionado, então continue. tracde B[n-1][M – W[n]].

Repita até chegar à linha 0 da tabela.

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

Nota: sempre que B[i][j] = B[i-1][j], o pacote i não está selecionado. O valor B[n][M] é o valor total ideal que cabe na mochila.

Passos para tracselecionando os pacotes escolhidos:

• Passo 1: Comece em i = n, j = M.
• Passo 2: Examine a coluna j de baixo para cima até encontrar uma linha i onde B[i][j] > B[i-1][j]. Marque o pacote i como selecionado: Select[i] = true.
• Passo 3: Atualize j = j – W[i]. Se j > 0, retorne ao Passo 2, caso contrário, vá para o Passo 4.
• Passo 4: Imprima todos os pacotes marcados como selecionados.

Java Code

Os seguintes Java O método preenche B[][] de baixo para cima, imprime a tabela para inspeção e então tracsão os pacotes selecionados.

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: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

Função mochilaDyProg() em Java

Explicação do código:

1. Alocar tabela B[][] e inicialize todas as células com o valor 0.
2. Preencha B[][] de baixo para cima usando a recorrência da seção anterior.
3. Comece cada célula com o valor “pular pacote i”. B[i-1][j].
4. Se selecionar o pacote i for viável e fornecer um valor estritamente melhor, sobrescreva a célula.
5. Trace os itens selecionados da linha n de volta para a linha 0.
6. Sempre que o pacote n for escolhido, diminua a capacidade restante em W[n-1].

Nota de correção: o parâmetro mutado do trecho original M enquanto ainda lia B[n][M]A versão mais segura acima usa um cursor separado. j para o trace.

O Java O driver executa o algoritmo em dois exemplos práticos:

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

Resultado do 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

Resultado do 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

Complexidade de tempo e espaço do problema da mochila 0/1

• Complexidade temporal: O(n · M) — os dois loops aninhados percorrem n itens por M+1 estados de capacidade.
• Complexidade espacial: O(n · M) para a tabela completa, redutível a O(M) por keeping apenas a linha anterior quando tracNão é necessário o envio eletrônico de e-mail.

O tempo de execução é pseudo-polinômio: polinomial no valor de M, mas exponencial nos bits usados ​​para codificar M. É por isso que o problema da mochila 0/1 continua sendo NP-difícil, mesmo que a programação dinâmica seja eficiente na prática.

Aplicações do Problema da Mochila 0/1

• Carregamento de carga, empacotamento de contêineres e separação de pedidos em armazém, respeitando os limites de peso.
• Alocação orçamentária entre projetos de investimento com custo fixo e retorno esperado.
• Problemas de corte de estoque na fabricação que não permitem a separação de peças individuais.
• Esquemas criptográficos como o Merkle-Hellman, que se baseiam na dificuldade do teste da mochila.
• Agendamento com recursos limitados em computação em nuvem e alocação de tarefas na CPU.
• Seleção de características em aprendizado de máquina com um orçamento de características fixo.

Perguntas Frequentes