Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como soluções do problema da mochila podem ser usadas para resolver problemas reais e atuais?

+1 voto
100 visitas
perguntada Mar 9, 2015 em Engenharia por danielcajueiro (5,251 pontos)  
recategorizado Mar 28, 2015 por danielcajueiro
Compartilhe

1 Resposta

+3 votos
respondida Abr 7, 2015 por VAS (471 pontos)  
selecionada Abr 12, 2015 por danielcajueiro
 
Melhor resposta

O problema da mochila (Knapsack Problem ou Rucksack Problem) surgiu no artigo “Dantzig, G. B. Discrete-Variable Extremum Problems, Operations Research, Institute for Operations Research and the Management Sciences (INFORMS), 1957, 5 (2), 266-288” e, de maneira geral, a sua versão básica (0-1 Knapsack) comumente apresentada tem uma aplicação limitada na prática, quando observado isoladamente. Entretanto, a solução proporcionada por esse algoritmo é muitas vezes utilizada como um "atalho” em problemas de combinação que apresentam um número muito grande de soluções ruins. O que efetivamente é empregado na prática são as derivações do problema básico (Multiple Knapsack Problems, Quadratic Knapsack Problem, Multiobjective Knapsack Problems e outros), principalmente na área de produção ou manufatura para definir a alocação de recursos (Matéria-prima) entre os diversos tipos de produtos que podem ser fabricados.

...