DAA - Mochila Fracionária

O algoritmo Greedy pode ser entendido muito bem com um problema bem conhecido conhecido como problema da mochila. Embora o mesmo problema pudesse ser resolvido através do emprego de outras abordagens algorítmicas, a abordagem Greedy resolve o problema da mochila fracionária razoavelmente em um bom tempo. Vamos discutir o problema da mochila em detalhes.

Problema da mochila

Dado um conjunto de itens, cada um com um peso e um valor, determine um subconjunto de itens a serem incluídos em uma coleção de modo que o peso total seja menor ou igual a um determinado limite e o valor total seja o maior possível.

O problema da mochila está no problema de otimização combinatória. Ele aparece como um subproblema em muitos modelos matemáticos mais complexos de problemas do mundo real. Uma abordagem geral para problemas difíceis é identificar a restrição mais restritiva, ignorar as outras, resolver um problema de mochila e, de alguma forma, ajustar a solução para satisfazer as restrições ignoradas.

Formulários

Em muitos casos de alocação de recursos junto com alguma restrição, o problema pode ser derivado de uma forma semelhante ao problema da mochila. A seguir está um conjunto de exemplos.

Encontrando a maneira menos desperdiçadora de cortar matérias-primas
otimização de portfólio
Problemas de corte de estoque

Cenário de Problema

Um ladrão está roubando uma loja e pode carregar um peso máximo de Wem sua mochila. Existem n itens disponíveis na loja e peso dei^th item é w_i e seu lucro é p_i. Quais itens o ladrão deve levar?

Nesse contexto, os itens devem ser selecionados de forma que o ladrão carregue aqueles itens para os quais obterá o lucro máximo. Portanto, o objetivo do ladrão é maximizar o lucro.

Com base na natureza dos itens, os problemas da mochila são categorizados como

Mochila Fracionária
Knapsack

Mochila Fracionária

Nesse caso, os itens podem ser quebrados em pedaços menores, portanto, o ladrão pode selecionar frações dos itens.

De acordo com a declaração do problema,

tem n itens na loja
Peso de i^th item $ w_ {i}> 0 $
Lucro para i^th item $ p_ {i}> 0 $ e
A capacidade da mochila é W

Nesta versão do problema da mochila, os itens podem ser quebrados em pedaços menores. Então, o ladrão pode levar apenas uma fraçãox_i do i^th item.

$$ 0 \ leqslant x_ {i} \ leqslant 1 $$

o i^th o item contribui com o peso $ x_ {i} .w_ {i} $ para o peso total na mochila e o lucro $ x_ {i} .p_ {i} $ para o lucro total.

Portanto, o objetivo deste algoritmo é

$$ maximizar \: \ displaystyle \ sum \ limits_ {n = 1} ^ n (x_ {i} .p _ {} i) $$

sujeito a restrição,

$$ \ displaystyle \ sum \ limits_ {n = 1} ^ n (x_ {i} .w _ {} i) \ leqslant W $$

É claro que uma solução ótima deve preencher a mochila exatamente, caso contrário, poderíamos adicionar uma fração de um dos itens restantes e aumentar o lucro geral.

Assim, uma solução ótima pode ser obtida por

$$ \ displaystyle \ sum \ limits_ {n = 1} ^ n (x_ {i} .w _ {} i) = W $$

Neste contexto, primeiro precisamos classificar esses itens de acordo com o valor de $ \ frac {p_ {i}} {w_ {i}} $, de modo que $ \ frac {p_ {i} +1} {w_ {i } +1} $ ≤ $ \ frac {p_ {i}} {w_ {i}} $. Aqui,x é uma matriz para armazenar a fração de itens.

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

Análise

Se os itens fornecidos já estiverem classificados em uma ordem decrescente de $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $, então o whileloop leva um tempo em O(n); Portanto, o tempo total incluindo a classificação está emO(n logn).

Exemplo

Vamos considerar que a capacidade da mochila W = 60 e a lista de itens fornecidos são mostrados na tabela a seguir -

Item	UMA	B	C	D
Lucro	280	100	120	120
Peso	40	10	20	24
Proporção $ (\ frac {p_ {i}} {w_ {i}}) $	7	10	6	5

Como os itens fornecidos não são classificados com base em $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $. Após a classificação, os itens são mostrados na tabela a seguir.

Item	B	UMA	C	D
Lucro	100	280	120	120
Peso	10	40	20	24
Proporção $ (\ frac {p_ {i}} {w_ {i}}) $	10	7	6	5

Solução

Depois de classificar todos os itens de acordo com $ \ frac {p_ {i}} {w_ {i}} $. Primeiro tudo deB é escolhido como peso de Bé inferior à capacidade da mochila. Próximo itemA é escolhido, pois a capacidade disponível da mochila é maior que o peso do A. Agora,Cé escolhido como o próximo item. No entanto, o item todo não pode ser escolhido, pois a capacidade restante da mochila é menor que o peso deC.

Portanto, fração de C (ou seja, (60 - 50) / 20) é escolhido.

Agora, a capacidade da mochila é igual aos itens selecionados. Portanto, nenhum outro item pode ser selecionado.

O peso total dos itens selecionados é 10 + 40 + 20 * (10/20) = 60

E o lucro total é 100 + 280 + 120 * (10/20) = 380 + 60 = 440

Esta é a solução ideal. Não podemos obter mais lucro selecionando qualquer combinação diferente de itens.

↰ Previous page Next page ↱