modelo matemático atrelado ao problema da mochila é dado pelo seguinte equacionamento: Max Sujeito à x_(i)in 0,1 Uma alternativa para a obtenção da solução ótima através da resolução do problema de programação inteira é a aplicação da heuristica gulosa do problema da mochila. O algoritmo correspondente ao uso dessa heurística é dado pelos seguintes passos: 1. Ordenar os n itens candidatos a serem colocados na mochila, de capacidade b, em ordem decrescente de valor da razão r_(1)=(u_(i))/(v_(1)) para i=1,ldots ,n Para a nova ordem dos itens, utilize o indice j. 2. Inicialize a capacidade utilizada da mochila, isto é. Cap=b 3. Inicialize o conjunto de itens contidos na mochila com vazio, isto é, Itens=0 4. Inicialize a soma das utilidades, isto é soma ui=0. 5. Para j=1 até n: 6. Se (Cap_(-)usogt =volume do item na ordem i) 7. Inserir item na ordem j na variável Itens 8. Atualizar a capacidade disponive da mochila: Cap =Cap - volume do item na ordem j 9. Atualizar a soma das utilidades da mochila: som a_(n)ui=soma_(n)ui+utilidade do item na ordem j 10. Imprimir os valores contidos em Itens e Cap Aplique a heuristica gulosa para o seguinte conjunto de dados: # Dados do problema Utilidade de se colocar o item j na mochila. ui=[41,33,14,25,32,32,9,19] #Vetor de gasto de recursos do itemj vi=[47,40,17,27,34,23,5,44] # Capacidade da mochila b=100 Acercada solucão encontrada através da heuristica gulosa, assinale a alternativa correta:

Para resolver o problema usando a heurística gulosa, siga os passos fornecidos:<br /><br />1. **Ordenar os itens em ordem decrescente de valor da razão \( r_i = \frac{u_i}{v_i} \):**<br /> - \( r_1 = \frac{41}{47} \approx 0.872 \)<br /> - \( r_2 = \frac{33}{40} \approx 0.825 \)<br /> - \( r_3 = \frac{14}{17} \approx 0.824 \)<br /> - \( r_4 = \frac{25}{27} \approx 0.926 \)<br /> - \( r_5 = \frac{32}{34} \approx 0.941 \)<br /> - \( r_6 = \frac{32}{23} \approx 1.391 \)<br /> - \( r_7 = \frac{9}{5} = 1.8 \)<br /> - \( r_8 = \frac{19}{44} \approx 0.432 \)<br /><br /> Ordenando em ordem decrescente: \( [r_6, r_7, r_5, r_4, r_1, r_2, r_3, r_8] \)<br /><br />2. **Inicializar variáveis:**<br /> - Capacidade utilizada: \( Cap = 100 \)<br /> - Conjunto de itens: \( Itens = [] \)<br /> - Soma das utilidades: \( soma = 0 \)<br /><br />3. **Iterar pelos itens em ordem:**<br /> - Para \( j = 1 \):<br /> - \( Cap_{uso} = 100 \)<br /> - Se \( Cap_{uso} \geq vi[j] \):<br /> - Inserir item na ordem j: \( Itens = [j] \)<br /> - Atualizar capacidade disponível: \( Cap = Cap - vi[j] \)<br /> - Atualizar soma das utilidades: \( soma = soma + ui[j] \)<br /><br /> - Para \( j = 2 \):<br /> - \( Cap_{uso} = 100 - 47 = 53 \)<br /> - Se \( Cap_{uso} \geq vi[j] \):<br /> - Inserir item na ordem j: \( Itens = [j, 1] \)<br /> - Atualizar capacidade disponível: \( Cap = Cap - vi[j] \)<br /> - Atualizar soma das utilidades: \( soma = soma + ui[j] \)<br /><br /> - Para \( j = 3 \):<br /> - \( Cap_{uso} = 53 - 33 = 20 \)<br /> - Se \( Cap_{uso} \geq vi[j] \):<br /> - Inserir item na ordem j: \( Itens = [j, 1, 2] \)<br /> - Atualizar capacidade disponível: \( Cap = Cap - vi[j] \)<br /> - Atualizar soma das utilidades: \( soma = soma + ui[j] \)<br /><br /> - Para \( j = 4 \):<br /> - \( Cap_{uso} = 20 - 14 = 6 \)<br /> - Se \( Cap_{uso} \geq vi[j] \):<br /> - Inserir item na ordem j: \( Itens = [j, 1, 2, 3] \)<br /> - Atualizar capacidade disponível: \( Cap = Cap - vi[j] \)<br /> - Atualizar soma das utilidades: \( soma = soma + ui[j] \)<br /><br /> - Para \( j = 5 \):<br /> - \( Cap_{uso} = 6 - 25 = -19 \)<br /> - Não é possível inserir mais itens, pois a capacidade não é suficiente.<br /><br />4. **Resultado final:**<br /> - Itens na mochila: \( Itens = [6, 7, 5, 4, 1] \)<br /> - Capacidade utilizada: \( Cap = 100 - 47 - 33 - 14 - 25 = 0 \)<br /> - Soma das utilidades: \( soma = 41 + 33 + 32 + 25 + 32 = 143 \)<br /><br />Portanto, a alternativa correta é:<br /><br />**Itens na mochila: [6, 7, 5, 4, 1], Capacidade utilizada: 0, Soma das utilidades: 143**