O problema da mochila fracionária em C++ refere-se a identificar uma forma de encher uma sacola com itens de determinado peso e lucro de forma que a sacola contenha o valor máximo sem ultrapassar o limite máximo.
Como resolver o problema da mochila fracionária em C++
Dado um conjunto de itens, cada um com peso e lucro determinados, determine cada número de itens em uma combinação tal que o peso total dos itens seja menor que o limite máximo da sacola, mas o valor deve ser mantido o maior possível.
Algoritmo para implementar o problema da mochila fracionária
O funcionamento do algoritmo Mochila pode ser entendido através dos seguintes pontos:
- Pegue duas matrizes de peso e lucro.
- Defina o valor máximo do saco para W.
- Determine a densidade tomando a proporção de ambos os parâmetros.
- Classifique os itens em ordem decrescente de densidade.
- Some os valores até que seja <=W.
A abordagem gananciosa para resolver o problema da mochila fracionária
A abordagem gananciosa visa fazer escolhas ideais em cada etapa, levando à solução ideal no final. Resolve problemas passo a passo levando a conclusões em vez de concluir os resultados apenas no final. Este é um código-fonte para implementar uma solução para o problema da mochila fracionária em C++:
#incluir
usando espaço para nome padrão ;
estrutura Objeto {
interno valor, peso ;
Objeto ( interno valor, interno peso )
: valor ( valor ) , peso ( peso )
{
}
} ;
bool cmp ( estrutura Objeto x, estrutura Objeto y )
{
dobro A1 = ( dobro ) x. valor / x. peso ;
dobro A2 = ( dobro ) e. valor / e. peso ;
retornar A1 > A2 ;
}
dobro fracionáriaMochila ( estrutura Chegada do objeto [ ] ,
interno EM, interno tamanho )
{
organizar ( arr, arr + tamanho, cmp ) ;
interno peso atual = 0 ;
dobro valor final = 0,0 ;
para ( interno eu = 0 ; eu < tamanho ; eu ++ ) {
se ( peso atual + chega [ eu ] . peso <= EM ) {
peso atual + = chega [ eu ] . peso ;
valor final + = chega [ eu ] . valor ;
}
outro {
interno permanecer = EM - peso atual ;
valor final + = chega [ eu ] . valor
* ( ( dobro ) permanecer
/ chega [ eu ] . peso ) ;
quebrar ;
}
}
retornar valor final ;
}
interno em = 60 ;
Chegada do objeto [ ] = { { 100 , vinte } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
interno tamanho = tamanho de ( chega ) / tamanho de ( chega [ 0 ] ) ;
corte << 'Lucro máximo ='
<< fracionáriaMochila ( arr, v, tamanho ) ;
retornar 0 ;
}
Neste código, é definida uma estrutura de objeto que contém valores de peso e lucro armazenados. O bool cmp() é usado para fazer uma comparação entre dois objetos com base na proporção entre peso e valor de dois objetos. A matriz é organizada em ordem decrescente e o valor continua somando até atingir o máximo. Se o valor atual for permitido e dentro do limite, ele é adicionado, caso contrário, sua proporção reduzida é adicionada ao saco. A magnitude do peso e do valor é inserida no código principal e o lucro máximo é impresso na saída.
O lucro máximo armazenado no lanche é 580.
Conclusão
O problema da mochila fracionária em C++ refere-se a identificar uma forma de encher uma sacola com itens de determinado peso e lucro de forma que a sacola contenha o valor máximo sem ultrapassar o limite máximo. Isto pode ser conseguido através da abordagem gananciosa que visa fazer escolhas ideais em cada etapa, levando à solução ideal no final.