Problema da mochila - Knapsack problem

Exemplo de um problema de mochila unidimensional (restrição): quais caixas devem ser escolhidas para maximizar a quantidade de dinheiro, mantendo o peso total menor ou igual a 15 kg? Um problema de múltiplas restrições pode levar em consideração o peso e o volume das caixas.
(Solução: se qualquer número de cada caixa estiver disponível, três caixas amarelas e três caixas cinzas; se apenas as caixas mostradas estiverem disponíveis, todas, exceto a caixa verde.)

O problema da mochila é um problema de otimização combinatória : dado um conjunto de itens, cada um com um peso e um valor, determine o número de cada item a incluir em uma coleção de modo que o peso total seja menor ou igual a um determinado limite e o valor total é o maior possível. Seu nome deriva do problema enfrentado por alguém que está preso a uma mochila de tamanho fixo e deve enchê-la com os itens mais valiosos. O problema geralmente surge na alocação de recursos, onde os tomadores de decisão têm que escolher entre um conjunto de projetos ou tarefas não divisíveis sob um orçamento fixo ou restrição de tempo, respectivamente.

O problema da mochila foi estudado por mais de um século, com os primeiros trabalhos datando de 1897. O nome "problema da mochila" remonta aos primeiros trabalhos do matemático Tobias Dantzig (1884-1956) e refere-se ao lugar-comum problema de embalar os itens mais valiosos ou úteis sem sobrecarregar a bagagem.

Formulários

Os problemas da mochila aparecem nos processos de tomada de decisão do mundo real em uma ampla variedade de campos, como encontrar a maneira menos dispendiosa de cortar matérias-primas, seleção de investimentos e carteiras , seleção de ativos para securitização lastreada em ativos e geração de chaves para o Merkle – Hellman e outros criptossistemas de mochila .

Uma das primeiras aplicações dos algoritmos da mochila foi na construção e pontuação de testes nos quais os participantes têm a opção de escolher quais perguntas responder. Para pequenos exemplos, é um processo bastante simples fornecer aos participantes do teste essa escolha. Por exemplo, se um exame contém 12 perguntas, cada uma valendo 10 pontos, o candidato precisa responder apenas 10 perguntas para atingir a pontuação máxima possível de 100 pontos. No entanto, em testes com uma distribuição heterogênea de valores de pontos, é mais difícil fornecer escolhas. Feuerman e Weiss propuseram um sistema em que os alunos são submetidos a um teste heterogêneo com um total de 125 pontos possíveis. Os alunos são solicitados a responder a todas as perguntas da melhor maneira possível. Dos possíveis subconjuntos de problemas cujos valores de pontos totais somam 100, um algoritmo de mochila determinaria qual subconjunto dá a cada aluno a pontuação mais alta possível.

Um estudo de 1999 do Repositório de Algoritmos da Stony Brook University mostrou que, de 75 problemas algorítmicos, o problema da mochila era o 19º mais popular e o terceiro mais necessário depois das árvores de sufixo e o problema de empacotamento de lixo .

Definição

O problema mais comum a ser resolvido é o problema da mochila 0-1 , que restringe o número de cópias de cada tipo de item a zero ou um. Dado um conjunto de itens numerados de 1 a , cada um com um peso e um valor , juntamente com uma capacidade máxima de peso , ${\ displaystyle x_ {i}}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle w_ {i}}$${\ displaystyle v_ {i}}$${\ displaystyle W}$

maximizar ${\ displaystyle \ sum _ {i = 1} ^ {n} v_ {i} x_ {i}}$

sujeito a e .${\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq W}$${\ displaystyle x_ {i} \ in \ {0,1 \}}$

Aqui representa o número de instâncias do item a incluir na mochila. Informalmente, o problema é maximizar a soma dos valores dos itens da mochila para que a soma dos pesos seja menor ou igual à capacidade da mochila. ${\ displaystyle x_ {i}}$${\ displaystyle i}$

O problema da mochila limitada ( BKP ) remove a restrição de que há apenas um de cada item, mas restringe o número de cópias de cada tipo de item a um valor inteiro máximo não negativo : ${\ displaystyle x_ {i}}$${\ displaystyle c}$

maximizar ${\ displaystyle \ sum _ {i = 1} ^ {n} v_ {i} x_ {i}}$

sujeito a e${\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq W}$${\ displaystyle x_ {i} \ in \ {0,1,2, \ dots, c \}.}$

O problema da mochila ilimitada ( UKP ) não impõe um limite superior ao número de cópias de cada tipo de item e pode ser formulado como acima, exceto que a única restrição é que ele é um número inteiro não negativo. ${\ displaystyle x_ {i}}$

maximizar ${\ displaystyle \ sum _ {i = 1} ^ {n} v_ {i} x_ {i}}$

sujeito a e${\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq W}$${\ displaystyle x_ {i} \ geq 0, \ x_ {i} \ in \ mathbb {Z}.}$

Um exemplo do problema da mochila ilimitada é dado usando a figura mostrada no início deste artigo e o texto "se algum número de cada caixa estiver disponível" na legenda dessa figura.

Complexidade computacional

O problema da mochila é interessante do ponto de vista da ciência da computação por muitos motivos:

• A forma do problema de decisão do problema da mochila ( pode um valor de pelo menos V ser alcançado sem exceder o peso W ? ) É NP-completa , portanto, não há algoritmo conhecido correto e rápido (tempo polinomial) em todos os casos.
• Embora o problema de decisão seja NP-completo, o problema de otimização não é, sua resolução é pelo menos tão difícil quanto o problema de decisão, e não há algoritmo polinomial conhecido que possa dizer, dada uma solução, se ele é ótimo (o que significaria que não há solução com um V maior , resolvendo assim o problema de decisão NP-completo).
• Existe um algoritmo de tempo pseudo-polinomial que usa programação dinâmica .
• Existe um esquema de aproximação de tempo totalmente polinomial , que usa o algoritmo de tempo pseudo-polinomial como uma sub-rotina, descrito abaixo.
• Muitos casos que surgem na prática e "instâncias aleatórias" de algumas distribuições podem ser resolvidos com exatidão.

Há uma ligação entre os problemas de "decisão" e "otimização" em que se existe um algoritmo polinomial que resolve o problema de "decisão", então pode-se encontrar o valor máximo para o problema de otimização em tempo polinomial, aplicando este algoritmo iterativamente enquanto aumentando o valor de k. Por outro lado, se um algoritmo encontra o valor ótimo do problema de otimização em tempo polinomial, então o problema de decisão pode ser resolvido em tempo polinomial comparando o valor da saída da solução por este algoritmo com o valor de k. Portanto, ambas as versões do problema apresentam dificuldades semelhantes.

Um tema na literatura de pesquisa é identificar como as instâncias "difíceis" do problema da mochila se parecem, ou vistas de outra maneira, para identificar quais propriedades das instâncias na prática podem torná-las mais receptivas do que sugere seu pior caso de comportamento NP-completo. O objetivo de encontrar essas instâncias "difíceis" é para seu uso em sistemas de criptografia de chave pública , como o criptossistema de mochila Merkle-Hellman .

Além disso, é notável o fato de que a dureza do problema da mochila depende da forma de entrada. Se os pesos e lucros forem dados como inteiros, é fracamente NP-completo , enquanto é fortemente NP-completo se os pesos e lucros forem dados como números racionais. No entanto, no caso de pesos e lucros racionais, ele ainda admite um esquema de aproximação de tempo totalmente polinomial .

Resolvendo

Vários algoritmos estão disponíveis para resolver problemas de mochila, com base na abordagem de programação dinâmica, a abordagem branch and bound ou hibridizações de ambas as abordagens.

Algoritmo avançado de programação dinâmica

O problema da mochila ilimitada ( UKP ) não restringe o número de cópias de cada tipo de item. Além disso, aqui assumimos que${\ displaystyle x_ {i}> 0}$

${\ displaystyle m [w '] = \ max \ left (\ sum _ {i = 1} ^ {n} v_ {i} x_ {i} \ right)}$

sujeito a e${\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq w '}$${\ displaystyle x_ {i}> 0}$

Observe que possui as seguintes propriedades: ${\ displaystyle m [w]}$

1. (a soma de zero itens, ou seja, a soma do conjunto vazio). ${\ displaystyle m [0] = 0 \, \!}$

2 . ,, onde é o valor do -ésimo tipo de item. ${\ displaystyle m [w] = \ max (v_ {1} + m [w-w_ {1}], v_ {2} + m [w-w_ {2}], ..., v_ {n} + m [w-w_ {n}])}$${\ displaystyle w_ {i} \ leq w}$${\ displaystyle v_ {i}}$${\ displaystyle i}$

A segunda propriedade precisa ser explicada em detalhes. Durante o processo de execução deste método, como obtemos o peso ? Existem apenas maneiras e os pesos anteriores são onde existem tipos totais de itens diferentes (ao dizer diferente, queremos dizer que o peso e o valor não são completamente os mesmos). Se conhecermos cada valor desses itens e o valor máximo relacionado anteriormente, apenas os comparamos e obtemos o valor máximo e pronto. ${\ displaystyle w}$${\ displaystyle i}$${\ displaystyle w-w_ {1}, w-w_ {2}, ..., w-w_ {i}}$${\ displaystyle i}$${\ displaystyle i}$

Aqui, o máximo do conjunto vazio é considerado zero. Tabular os resultados de cima para baixo fornece a solução. Como o cálculo de cada um envolve o exame de no máximo itens e há no máximo valores de para calcular, o tempo de execução da solução de programação dinâmica é . Dividir por seu maior divisor comum é uma forma de melhorar o tempo de execução. ${\ displaystyle m [0]}$${\ displaystyle m [W]}$${\ displaystyle m [w]}$${\ displaystyle n}$${\ displaystyle W}$${\ displaystyle m [w]}$${\ displaystyle O (nW)}$${\ displaystyle w_ {1}, \, w_ {2}, \, \ ldots, \, w_ {n}, \, W}$

Mesmo se P ≠ NP , a complexidade não contradiz o fato de que o problema da mochila é NP-completo , uma vez que , ao contrário , não é polinomial no comprimento da entrada para o problema. O comprimento da entrada para o problema é proporcional ao número de bits em , e não a ele mesmo. No entanto, como esse tempo de execução é pseudopolinomial , isso torna o problema da mochila (versão de decisão do) um problema NP-completo fraco . ${\ displaystyle O (nW)}$${\ displaystyle W}$${\ displaystyle n}$${\ displaystyle W}$${\ displaystyle W}$${\ displaystyle \ log W}$${\ displaystyle W}$

0-1 problema de mochila

Uma solução de programação dinâmica semelhante para o problema da mochila 0-1 também funciona em tempo pseudo-polinomial. Suponha que sejam inteiros estritamente positivos. Defina como o valor máximo que pode ser atingido com peso menor ou igual ao uso de itens até (primeiros itens). ${\ displaystyle w_ {1}, \, w_ {2}, \, \ ldots, \, w_ {n}, \, W}$${\ displaystyle m [i, w]}$${\ displaystyle w}$${\ displaystyle i}$${\ displaystyle i}$

Podemos definir recursivamente da seguinte forma: (Definição A)${\ displaystyle m [i, w]}$

• ${\ displaystyle m [0, \, w] = 0}$
• ${\ displaystyle m [i, \, w] = m [i-1, \, w]}$se (o novo item é mais do que o limite de peso atual)${\ displaystyle w_ {i}> w \, \!}$
• ${\ displaystyle m [i, \, w] = \ max (m [i-1, \, w], \, m [i-1, w-w_ {i}] + v_ {i})}$se .${\ displaystyle w_ {i} \ leqslant w}$

A solução pode então ser encontrada por meio de cálculos . Para fazer isso de forma eficiente, podemos usar uma tabela para armazenar cálculos anteriores. ${\ displaystyle m [n, W]}$

A seguir está o pseudocódigo para o programa dinâmico:

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.

array m[0..n, 0..W];
for j from 0 to W do:
    m[0, j] := 0
for i from 1 to n do:
    m[i, 0] := 0

for i from 1 to n do:
    for j from 0 to W do:
        if w[i] > j then:
            m[i, j] := m[i-1, j]
        else:
            m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

Esta solução será executada no tempo e no espaço. (Se precisarmos apenas do valor m [n, W], podemos modificar o código para que a quantidade de memória necessária seja O (W) que armazena as duas linhas recentes do array "m".) ${\ displaystyle O (nW)}$${\ displaystyle O (nW)}$

No entanto, se dermos um ou dois passos adiante, devemos saber que o método será executado entre e . A partir da Definição A , podemos saber que não há necessidade de calcular todos os pesos quando o número de itens e os próprios itens que escolhemos são fixos. Ou seja, o programa acima calcula mais do que o necessário porque o peso muda de 0 para W o tempo todo. Desta perspectiva, podemos programar este método para que seja executado recursivamente. ${\ displaystyle O (nW)}$${\ displaystyle O (2 ^ {n})}$

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.

Define value[n, W]

Initialize all value[i, j] = -1

Define m:=(i,j)         // Define function m so that it represents the maximum value we can get under the condition: use first i items, total weight limit is j
{
    if i == 0 or j <= 0 then:
        value[i, j] = 0
        return

    if (value[i-1, j] == -1) then:     // m[i-1, j] has not been calculated, we have to call function m
        value[i-1, j] = m(i-1, j)

    if w[i] > j then:                      // item cannot fit in the bag
        value[i, j] = value[i-1, j]
    else: 
        if (value[i-1, j-w[i]] == -1) then:     // m[i-1,j-w[i]] has not been calculated, we have to call function m
            value[i-1, j-w[i]] = m(i-1, j-w[i])
        value[i, j] = max(value[i-1,j], value[i-1, j-w[i]] + v[i])
}

Run m(n, W)

Por exemplo, existem 10 itens diferentes e o limite de peso é 67. Então,

${\ displaystyle {\ begin {alinhados} & w [1] = 23, w [2] = 26, w [3] = 20, w [4] = 18, w [5] = 32, w [6] = 27 , w [7] = 29, w [8] = 26, w [9] = 30, w [10] = 27 \\ & v [1] = 505, v [2] = 352, v [3] = 458 , v [4] = 220, v [5] = 354, v [6] = 414, v [7] = 498, v [8] = 545, v [9] = 473, v [10] = 543 \ \\ end {alinhado}}}$

Se você usar o método acima para calcular , você obterá isso, excluindo chamadas que produzem : ${\ displaystyle m (10,67)}$${\ displaystyle m (i, j) = 0}$

${\ displaystyle {\ begin {alinhados} & m (10,67) = 1270 \\ & m (9,67) = 1270, m (9,40) = 678 \\ & m (8,67) = 1270, m (8 , 40) = 678, m (8,37) = 545 \\ & m (7,67) = 1183, m (7,41) = 725, m (7,40) = 678, m (7,37) = 505 \\ & m (6,67) = 1183, m (6,41) = 725, m (6,40) = 678, m (6,38) = 678, m (6,37) = 505 \\ & m (5,67) = 1183, m (5,41) = 725, m (5,40) = 678, m (5,38) = 678, m (5,37) = 505 \\ & m (4,67 ) = 1183, m (4,41) = 725, m (4,40) = 678, m (4,38) = 678, m (4,37) = 505, m (4,35) = 505 \\ & m (3,67) = 963, m (3,49) = 963, m (3,41) = 505, m (3,40) = 505, m (3,38) = 505, m (3,37 ) = 505, m (3,35) = 505, m (3,23) = 505, m (3,22) = 458, m (3,20) = 458 \\ & m (2,67) = 857, m (2,49) = 857, m (2,47) = 505, m (2,41) = 505, m (2,40) = 505, m (2,38) = 505, m (2,37 ) = 505, m (2,35) = 505, m (2,29) = 505, m (2,23) = 505 \\ & m (1,67) = 505, m (1,49) = 505, m (1,47) = 505, m (1,41) = 505, m (1,40) = 505, m (1,38) = 505, m (1,37) = 505, m (1,35 ) = 505, m (1,29) = 505, m (1,23) = 505 \\\ fim {alinhado}}}$

Além disso, podemos quebrar a recursão e convertê-la em uma árvore. Então, podemos cortar algumas folhas e usar a computação paralela para agilizar a execução desse método.

Para encontrar o subconjunto real de itens, em vez de apenas seu valor total, podemos executar isso depois de executar a função acima:

/**
 * Returns the indices of the items of the optimal knapsack.
 * i: We can include items 1 through i in the knapsack
 * j: maximum weight of the knapsack
 */
function knapsack(i: int, j: int): Set<int> {
    if i == 0 then:
        return {}
    if m[i, j] > m[i-1, j] then:
        return {i} ∪ knapsack(i-1, j-w[i])
    else:
        return knapsack(i-1, j)
}

knapsack(n, W)

Meet-in-the-middle

Outro algoritmo para mochila 0-1, descoberto em 1974 e às vezes chamado de "encontro no meio" devido aos paralelos com um algoritmo de nome semelhante em criptografia , é exponencial no número de itens diferentes, mas pode ser preferível ao algoritmo DP quando é grande em comparação com n . Em particular, se forem não negativos, mas não inteiros, ainda poderíamos usar o algoritmo de programação dinâmica por escala e arredondamento (ou seja, usando aritmética de ponto fixo ), mas se o problema exigir dígitos fracionários de precisão para chegar à resposta correta, será necessário para ser escalado , e o algoritmo DP exigirá espaço e tempo. ${\ displaystyle W}$${\ displaystyle w_ {i}}$${\ displaystyle d}$${\ displaystyle W}$${\ displaystyle 10 ^ {d}}$${\ displaystyle O (W10 ^ {d})}$${\ displaystyle O (nW10 ^ {d})}$

algorithm Meet-in-the-middle is
    input: A set of items with weights and values.
    output: The greatest combined value of a subset.

    partition the set {1...n} into two sets A and B of approximately equal size
    compute the weights and values of all subsets of each set

    for each subset of A do
        find the subset of B of greatest value such that the combined weight is less than W

    keep track of the greatest combined value seen so far

O algoritmo ocupa espaço e implementações eficientes da etapa 3 (por exemplo, ordenando os subconjuntos de B por peso, descartando subconjuntos de B que pesam mais do que outros subconjuntos de B de valor maior ou igual e usando pesquisa binária para encontrar a melhor correspondência ) resulta em um tempo de execução de . Tal como acontece com o ataque meet in the middle na criptografia, isso melhora o tempo de execução de uma abordagem ingênua de força bruta (examinando todos os subconjuntos de ), ao custo de usar espaço exponencial em vez de constante (ver também passo gigante ). ${\ displaystyle O (2 ^ {n / 2})}$${\ displaystyle O (n2 ^ {n / 2})}$${\ displaystyle O (n2 ^ {n})}$${\ displaystyle \ {1 ... n \}}$

Algoritmos de aproximação

Como para a maioria dos problemas NP-completos, pode ser suficiente encontrar soluções viáveis, mesmo que não sejam ótimas. De preferência, porém, a aproximação vem com a garantia da diferença entre o valor da solução encontrada e o valor da solução ótima.

Tal como acontece com muitos algoritmos úteis, mas computacionalmente complexos, tem havido pesquisas substanciais sobre a criação e análise de algoritmos que se aproximam de uma solução. O problema da mochila, embora NP-Hard, faz parte de uma coleção de algoritmos que ainda podem ser aproximados em qualquer grau especificado. Isso significa que o problema possui um esquema de aproximação de tempo polinomial. Para ser exato, o problema da mochila tem um esquema de aproximação de tempo totalmente polinomial (FPTAS).

Algoritmo de aproximação ganancioso

George Dantzig propôs um algoritmo de aproximação ganancioso para resolver o problema da mochila ilimitada. Sua versão classifica os itens em ordem decrescente de valor por unidade de peso . Em seguida, passa a inseri-los no saco, começando com o maior número possível de cópias do primeiro tipo de item, até que não haja mais espaço no saco para mais. Contanto que haja um suprimento ilimitado de cada tipo de item, se for o valor máximo de itens que cabem no saco, o algoritmo guloso terá garantia de atingir pelo menos um valor de . ${\ displaystyle v_ {1} / w_ {1} \ geq \ cdots \ geq v_ {n} / w_ {n}}$${\ displaystyle m}$${\ displaystyle m / 2}$

Para o problema limitado, onde a oferta de cada tipo de item é limitada, o algoritmo acima pode estar longe de ser ótimo. No entanto, uma modificação simples nos permite resolver este caso: Suponha, para simplificar, que todos os itens cabem individualmente no saco ( para todos ). Construa uma solução empacotando avidamente os itens pelo maior tempo possível, ou seja, onde . Além disso, construa uma segunda solução contendo o primeiro item que não se encaixou. Uma vez que fornece um limite superior para o relaxamento LP do problema, um dos conjuntos deve ter pelo menos valor ; portanto, retornamos o que for e tiver o melhor valor para obter uma -aproximação. ${\ displaystyle w_ {i} \ leq W}$${\ displaystyle i}$${\ displaystyle S_ {1}}$${\ displaystyle S_ {1} = \ left \ {1, \ ldots, k \ right \}}$${\ displaystyle k = \ textstyle \ max _ {1 \ leq k '\ leq n} \ textstyle \ sum _ {i = 1} ^ {k'} w_ {i} \ leq W}$${\ displaystyle S_ {2} = \ left \ {k + 1 \ right \}}$${\ displaystyle S_ {1} \ cup S_ {2}}$${\ displaystyle m / 2}$${\ displaystyle S_ {1}}$${\ displaystyle S_ {2}}$${\ displaystyle 1/2}$

Esquema de aproximação de tempo totalmente polinomial

O esquema de aproximação de tempo totalmente polinomial (FPTAS) para o problema da mochila tira vantagem do fato de que a razão do problema não ter soluções de tempo polinomial conhecidas é porque os lucros associados aos itens não são restritos. Se alguém arredondar alguns dos dígitos menos significativos dos valores de lucro, eles serão limitados por um polinômio e 1 / ε, onde ε é um limite para a correção da solução. Essa restrição significa que um algoritmo pode encontrar uma solução em tempo polinomial que seja correta dentro de um fator de (1-ε) da solução ótima.

algorithm FPTAS is 
    input: ε ∈ (0,1]
            a list A of n items, specified by their values, ${\displaystyle v_{i}}$, and weights
    output: S' the FPTAS solution

    P := max ${\displaystyle \{v_{i}\mid 1\leq i\leq n\}}$  // the highest item value
    K := ε ${\displaystyle {\frac {P}{n}}}$

    for i from 1 to n do
        ${\displaystyle v'_{i}}$ := ${\displaystyle \left\lfloor {\frac {v_{i}}{K}}\right\rfloor }$
    end for

    return the solution, S', using the ${\displaystyle v'_{i}}$ values in the dynamic program outlined above

Teorema: O conjunto calculado pelo algoritmo acima satisfaz , onde é uma solução ótima. ${\ displaystyle S '}$${\ displaystyle \ mathrm {lucro} (S ') \ geq (1- \ varejpsilon) \ cdot \ mathrm {lucro} (S ^ {*})}$${\ displaystyle S ^ {*}}$

Relações de dominância

Resolver o problema da mochila ilimitada pode ser facilitado jogando fora itens que nunca serão necessários. Para um determinado item , suponha que pudéssemos encontrar um conjunto de itens em que seu peso total seja menor que o peso de e seu valor total seja maior que o valor de . Então, não pode aparecer na solução ótima, porque sempre poderíamos melhorar qualquer solução potencial que contém , substituindo pelo conjunto . Portanto, podemos desconsiderar o -ésimo item completamente. Em tais casos, é dito que domina . (Observe que isso não se aplica a problemas de mochila limitada, uma vez que podemos já ter usado os itens em .) ${\ displaystyle i}$${\ displaystyle J}$${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle J}$${\ displaystyle i}$${\ displaystyle J}$ ${\ displaystyle i}$${\ displaystyle J}$

Encontrar relações de dominância nos permite reduzir significativamente o tamanho do espaço de busca. Existem vários tipos diferentes de relações de dominância , que satisfazem uma desigualdade da forma:

${\ displaystyle \ qquad \ sum _ {j \ in J} w_ {j} \, x_ {j} \ \ leq \ alpha \, w_ {i}}$, e para alguns${\ displaystyle \ sum _ {j \ in J} v_ {j} \, x_ {j} \ \ geq \ alpha \, v_ {i} \,}$${\ displaystyle x \ in Z _ {+} ^ {n}}$

onde e . O vetor denota o número de cópias de cada membro de . ${\ displaystyle \ alpha \ in Z _ {+} \ ,, J \ subsetneq N}$${\ displaystyle i \ not \ in J}$${\ displaystyle x}$${\ displaystyle J}$

Dominância coletiva

O -ésimo item é dominado coletivamente por , escrito como , se o peso total de alguma combinação de itens em for menor que w _i e seu valor total for maior que v _i . Formalmente, e para alguns , ou seja . Verificar essa dominância é computacionalmente difícil, portanto, só pode ser usado com uma abordagem de programação dinâmica. Na verdade, isso é equivalente a resolver um problema de decisão de mochila menor , onde , e os itens são restritos .${\ displaystyle i}$${\ displaystyle J}$${\ displaystyle i \ ll J}$${\ displaystyle J}$${\ displaystyle \ sum _ {j \ in J} w_ {j} \, x_ {j} \ \ leq w_ {i}}$${\ displaystyle \ sum _ {j \ in J} v_ {j} \, x_ {j} \ \ geq v_ {i}}$${\ displaystyle x \ in Z _ {+} ^ {n}}$${\ displaystyle \ alpha = 1}$${\ displaystyle V = v_ {i}}$${\ displaystyle W = w_ {i}}$${\ displaystyle J}$

Dominância de limiar

O -ésimo item é o limiar dominado por , escrito como se algum número de cópias de fosse dominado por . Formalmente, e para alguns e . Esta é uma generalização da dominância coletiva, introduzida e usada pela primeira vez no algoritmo EDUK. O menor deles define o limite do item , escrito . Nesse caso, a solução ótima poderia conter no máximo cópias de .${\ displaystyle i}$${\ displaystyle J}$${\ displaystyle i \ prec \ prec J}$${\ displaystyle i}$${\ displaystyle J}$${\ displaystyle \ sum _ {j \ in J} w_ {j} \, x_ {j} \ \ leq \ alpha \, w_ {i}}$${\ displaystyle \ sum _ {j \ in J} v_ {j} \, x_ {j} \ \ geq \ alpha \, v_ {i} \,}$${\ displaystyle x \ in Z _ {+} ^ {n}}$${\ displaystyle \ alpha \ geq 1}$${\ displaystyle \ alpha}$${\ displaystyle i}$${\ displaystyle t_ {i} = (\ alpha -1) w_ {i}}$${\ displaystyle \ alpha -1}$${\ displaystyle i}$

Domínio múltiplo

O -ésimo item é multiplicado por um único item , escrito como se fosse dominado por um certo número de cópias de . Formalmente, e para alguns ie . Essa dominância pode ser usada com eficiência durante o pré-processamento porque pode ser detectada com relativa facilidade.${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle i \ ll _ {m} j}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle w_ {j} \, x_ {j} \ \ leq w_ {i}}$${\ displaystyle v_ {j} \, x_ {j} \ \ geq v_ {i}}$${\ displaystyle x_ {j} \ in Z _ {+}}$${\ displaystyle J = \ {j \}, \ alpha = 1, x_ {j} = \ lfloor {\ frac {w_ {i}} {w_ {j}}} \ rfloor}$

Dominância modular

Deixe ser o melhor item , ou seja, para todos . Este é o item com maior densidade de valor. O -ésimo item é modularmente dominado por um único item , escrito como se fosse dominado por várias cópias de . Formalmente, e ie .${\ displaystyle b}$${\ displaystyle {\ frac {v_ {b}} {w_ {b}}} \ geq {\ frac {v_ {i}} {w_ {i}}} \,}$${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle i \ ll _ {\ equiv} j}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle b}$${\ displaystyle w_ {j} + tw_ {b} \ leq w_ {i}}$${\ displaystyle v_ {j} + tv_ {b} \ geq v_ {i}}$${\ displaystyle J = \ {b, j \}, \ alpha = 1, x_ {b} = t, x_ {j} = 1}$

Variações

Existem muitas variações do problema da mochila que surgiram do vasto número de aplicações do problema básico. As principais variações ocorrem pela alteração do número de algum parâmetro do problema como o número de itens, número de objetivos ou mesmo o número de mochilas.

Problema de mochila multi-objetivo

Essa variação muda o objetivo do indivíduo no preenchimento da mochila. Em vez de um objetivo, como maximizar o lucro monetário, o objetivo pode ter várias dimensões. Por exemplo, pode haver preocupações ambientais ou sociais, bem como objetivos econômicos. Os problemas frequentemente tratados incluem otimizações de portfólio e logística de transporte.

Por exemplo, suponha que você administre um navio de cruzeiro. Você tem que decidir quantos comediantes famosos contratar. Este barco não pode transportar mais de uma tonelada de passageiros e os artistas devem pesar menos de 1000 libras. Cada comediante tem um peso, traz negócios com base em sua popularidade e pede um salário específico. Neste exemplo, você tem vários objetivos. Obviamente, você deseja maximizar a popularidade de seus artistas e, ao mesmo tempo, minimizar seus salários. Além disso, você deseja ter o maior número possível de artistas.

Problema de mochila multidimensional

Nesta variação, o peso da mochila é dado por um vetor D-dimensional e a mochila tem um vetor de capacidade D-dimensional . A meta é maximizar a soma dos valores dos itens da mochila para que a soma dos pesos em cada dimensão não ultrapasse . ${\ displaystyle i}$${\ displaystyle {\ overline {w_ {i}}} = (w_ {i1}, \ ldots, w_ {iD})}$${\ displaystyle (W_ {1}, \ ldots, W_ {D})}$${\ displaystyle d}$${\ displaystyle W_ {d}}$

A mochila multidimensional é computacionalmente mais difícil do que a mochila; mesmo para , o problema não tem EPTAS a menos que P NP. No entanto, o algoritmo em é mostrado para resolver instâncias esparsas com eficiência. Uma instância de mochila multidimensional é esparsa se houver um conjunto de tal que para cada item de mochila , tal que e . Essas instâncias ocorrem, por exemplo, ao programar pacotes em uma rede sem fio com nós de retransmissão. O algoritmo também resolve instâncias esparsas da variante de múltipla escolha, mochila multidimensional de múltipla escolha. ${\ displaystyle D = 2}$${\ displaystyle =}$${\ displaystyle J = \ {1,2, \ ldots, m \}}$${\ displaystyle m <D}$${\ displaystyle i}$${\ displaystyle \ exists z> m}$${\ displaystyle \ forall j \ in J \ cup \ {z \}, \ w_ {ij} \ geq 0}$${\ displaystyle \ forall y \ notin J \ cup \ {z \}, w_ {iy} = 0}$

O algoritmo IHS (Aumentar a Prateleira de Altura) é ideal para mochila 2D (quadrados de embalagem em um quadrado de tamanho de unidade bidimensional): quando há no máximo cinco quadrados em uma embalagem ideal.

Problema de mochila múltipla

Esta variação é semelhante ao problema de empacotamento do compartimento . Ele difere do Problema de Embalagem da Caixa porque um subconjunto de itens pode ser selecionado, ao passo que, no Problema de Embalagem da Caixa, todos os itens devem ser embalados em determinadas caixas. O conceito é que existem várias mochilas. Isso pode parecer uma mudança trivial, mas não é equivalente a aumentar a capacidade da mochila inicial. Esta variação é usada em muitos problemas de carregamento e programação em Pesquisa Operacional e tem um esquema de aproximação de tempo polinomial .

Problema de mochila quadrática

O problema da mochila quadrática maximiza uma função objetivo quadrática sujeita a restrições de capacidade binárias e lineares. O problema foi introduzido por Gallo, Hammer e Simeone em 1980; no entanto, o primeiro tratamento do problema remonta a Witzgall em 1975.

Problema de subconjunto de soma

O problema da soma do subconjunto é um caso especial da decisão e 0-1 problemas onde cada tipo de item, o peso é igual ao valor: . No campo da criptografia , o termo problema da mochila é freqüentemente usado para se referir especificamente ao problema da soma do subconjunto e é comumente conhecido como um dos 21 problemas NP-completos de Karp . ${\ displaystyle w_ {i} = v_ {i}}$

A generalização do problema da soma do subconjunto é chamada de problema da soma do subconjunto múltiplo, no qual existem vários compartimentos com a mesma capacidade. Foi demonstrado que a generalização não possui um FPTAS .

Problema de mochila geométrica

No problema da mochila geométrica , existe um conjunto de retângulos com valores diferentes e uma mochila retangular. O objetivo é colocar o maior valor possível na mochila.

Veja também

Notas

Referências

• Garey, Michael R .; David S. Johnson (1979). Computadores e intratabilidade: um guia para a teoria da NP-completude . WH Freeman. ISBN 978-0-7167-1045-5. A6: MP9, pág.247.
• Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Problemas com a mochila . Springer. doi : 10.1007 / 978-3-540-24777-7 . ISBN 978-3-540-40286-2. MR  2161720 .
• Martello, Silvano; Toth, Paolo (1990). Problemas da mochila: Algoritmos e implementações informáticas . Wiley-Interscience. ISBN 978-0-471-92420-3. MR  1086874 .

links externos

• Descarregue gratuitamente o livro "Problemas da mochila: Algoritmos e implementações informáticas", de Silvano Martello e Paolo Toth
• Slides de aula sobre o problema da mochila
• PYAsUKP: Mais um solucionador para o problema da mochila sem limites , com código aproveitando as relações de dominância em um algoritmo híbrido, benchmarks e cópias para download de alguns artigos.
• Página inicial de David Pisinger com cópias para download de alguns artigos da lista de publicações (incluindo "Onde estão os problemas difíceis da mochila?")
• Soluções de problemas da mochila em vários idiomas na Rosetta Code
• Algoritmo de programação dinâmica para 0/1 problema de mochila
• Solucionador de problemas de mochila (online)
• Resolvendo 0-1-KNAPSACK com Algoritmos Genéticos em Ruby Arquivado em 23 de maio de 2011 na Wayback Machine
• Códigos para problema de mochila quadrática

• Otimizando a embalagem tridimensional do escaninho
• Solução de programação inteira de mochila em Python Gekko (software de otimização)