Mochila Fracionária por Proporção
Escolha primeiro o maior valor por peso.
Mochila Fracionária por Proporção é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
A configuração da mochila
Você tem itens com um valor e um peso, além de uma mochila com capacidade limitada. O objetivo é transportar o maior valor total possível. 🎒
Fracionário significa divisível
Na versão fracionária, você pode pegar uma parte de um item, como metade de um saco de grãos. Essa liberdade é o que permite ao algoritmo guloso vencer aqui.
Valor por peso
A métrica principal é a razão entre o valor e o peso de cada item. Uma razão alta significa muito valor concentrado em pouquíssimo espaço.
ratio = value / weightOrdenar pela melhor razão
sort os itens pelo valor por peso, do maior para o menor. O plano guloso é continuar escolhendo o maior valor disponível por unidade de espaço.
items.sort(key=lambda i: i[0] / i[1], reverse=True)Pegue o item inteiro enquanto couber
Percorra a lista ordenada e pegue cada item inteiro se ele ainda couber na capacidade restante. Adicione seu valor total ao resultado.
if weight <= cap:
total += value
cap -= weightPreencher o último espaço
Quando um item for grande demais, pegue uma fração que preencha exatamente o espaço restante. Então a mochila estará cheia e você parará.
total += value * (cap / weight)Por que a ordem das razões funciona
Cada unidade de capacidade deve conter o maior valor possível, portanto o item de maior densidade precisa vir primeiro. Trocar por uma densidade menor apenas reduz o valor.
O problema da mochila 0/1 é diferente
Se os itens não puderem ser divididos, a estratégia gulosa pela proporção falha. A versão 0/1 exige programação dinâmica, não essa ordenação simples.
O tempo de execução
Ordenar pela proporção custa O(n log n), e o laço de preenchimento é linear. Isso é mais do que rápido o suficiente para os limites típicos de competições.
Tenha cuidado com a fração final
Use números de ponto flutuante ou racionais exatos para o item parcial. Truncar cedo pode reduzir o valor e causar uma resposta errada.
Onde isso aparece
Pense em carregar cargas, misturar combustíveis ou dividir recursos. Sempre que as partes forem divisíveis, a estratégia gulosa pela proporção é a sua ferramenta.
Verificação rápida
Você está preenchendo uma mochila no problema da mochila fracionária.
Recapitulação
Ordene os itens por valor por peso, pegue os itens inteiros enquanto eles couberem e, depois, uma fração para completar a mochila. Essa estratégia gulosa só é ótima quando os itens podem ser divididos. 🚀
Perguntas Frequentes
A aula “Mochila Fracionária por Proporção” é grátis?
Sim — o texto completo de “Mochila Fracionária por Proporção” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Mochila Fracionária por Proporção”?
Escolha primeiro o maior valor por peso. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Mochila Fracionária por Proporção”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- A Mentalidade Gulosa
- Seleção de Atividades pelo Término Mais Cedo
- Mochila Fracionária por Proporção
- Identifique Quando a Estratégia Gulosa Falha