Mochila fracionária em tempo linear

Seria bom se você declarasse o problema. Presumo que você tenha $ n $ itens $ x_i $ , cada um tendo lucro $ p_i $ e peso $ w_i $ . Você deseja maximizar seu lucro sob a restrição de que o peso total seja no máximo $ W $ . Para cada item $ x_i $ , você pode colocar qualquer fração $ \ theta \ em [0,1] $ dele, o que lhe dará lucro $ \ theta p_i $ e peso $ \ theta w_i $ .

Aqui está um exemplo. Você tem ouro bruto, com um lucro de $ 1000 $ e peso $ 1 $ . Você também tem bananas, com um lucro de $ 1 $ e peso $ 10 $ . Suponha que você possa carregar um peso de $ 2 $ . O que você faria? Naturalmente, você primeiro colocaria tanto ouro quanto pudesse – ou seja, todo ele, e então você colocaria tantas bananas quanto você pudesse – ou seja, um décimo dele, para um lucro total de $ 1000,1 $ .

O algoritmo geral é semelhante. Suponha que você divida $ W $ em $ 1000 $ “slots”, que deseja preencher com o máximo item-partes lucrativas de peso $ W / 1000 $ . Para um item pesando $ w_i $ , temos $ w_i / (W / 1000) $ peças (suponha por enquanto, é um número inteiro) e cada um deles vale $ p_i / (w_i / (W / 1000)) $ . Ao escolher o que colocar em um slot, gostaríamos de maximizar nosso lucro e, então, escolhemos o item com $ p_i / w_i $ máximo e colocamos tantos peças quanto possível. Se acabarmos, escolhemos o item com o próximo maior $ p_i / w_i $ e assim por diante.

Você pode implementar isso sem dividir $ W $ em um $ 1000 $ peças: Escolha o item com $ p_i / w_i $ , e coloque o máximo possível. Se você ficar sem, escolha o próximo e coloque o máximo possível. E assim por diante. A implementação deste algoritmo requer a classificação da lista $ p_i / w_i $ , o que leva tempo $ O (n \ log n) $ . O algoritmo que você descreve usa o mesmo truque usado na seleção rápida para reduzir o tempo de execução para $ O (n) $ , ao custo de tornar o algoritmo randomizado.

Eu sugiro o seguinte caminho para entender o algoritmo:

1. Compreenda o algoritmo guloso clássico para mochila fracionária.
2. Compreenda a seleção rápida.
3. Veja como o algoritmo que você cita combina a técnica de seleção rápida com a abordagem gananciosa.

R é o conjunto de razões de lucro / peso de cada objeto , onde o lucro e o peso dos objetos são dados. E W é a Capacidade da mochila .
Agora, em vez de escolher um elemento aleatório em uma etapa, podemos aplicar o algoritmo de localização mediana para encontre a mediana em O (n) vezes.
E então podemos seguir todas as etapas restantes.Portanto, a análise da complexidade do tempo será –
        T (n) = T (n / 2) + O (n).
E obteremos O (n) como solução. Diga-me se algo não estiver explicado corretamente e você quiser saber mais alguma coisa.

No tempo linear, você pode encontrar o item mediano em termos de valor por peso unitário. Então, também em tempo linear, você pode descobrir se pode colocar todos os itens que são pelo menos tão valiosos na mochila ou não. Se puder, faça-o e resolva recursivamente este problema para os n / 2 itens de menor valor, dado que você ” já encheu a mochila. Se não conseguir, pode jogar fora os n / 2 itens de menor valor, e tente resolver o problema novamente com apenas os n / 2 itens de maior valor.

A recorrência aqui é T (n) = T (n / 2) + O (n) , e nós temos isso T (n) = O (n) , conforme desejado.

Na solução que você colou: R é o conjunto de proporções, lucro / peso W é a soma de todo o peso deste conjunto , usado para comparar com a capacidade de sua mochila. Da mesma forma, {pi / wi | pi / wi} representa o i-ésimo elemento que o lucro é para o i-ésimo valor do peso. Estamos comparando esse valor ao valor r selecionado aleatoriamente e, em seguida, segregando com base na comparação da proporção. Os R1, R2, R3 são subconjuntos adicionais da proporção definida, dependendo da proporção ser menor, igual ou maior que a de o elemento mediano.

da mesma forma, W1, W2, W3 são a soma dos pesos desses conjuntos.

Agora escolha o conjunto de solução adequado dependendo dos valores de proporção conforme explicado no início.