Omodelo matemitico atrelado ao problema da mochila e dado pelo seguinte equacionamento Max sum _(n=1)^n1_(n)x_(1) x_(1)in 0,1 n=1,... ,N Uma alternativa para a obtencilo da solucilo otima atraves da resolução do problema de programacle inters e a aplicaclo da houristica guios sigortmo correspondente an use dessa heuristica e dado pelos seguintes passos 1. Ordenar os nitens candidatos a serem colocados na mochila, de capacidade In em ordern decrescents do valor da nuile x_(1)=(u_(1))/(x_(1)) int. itens, utilize o indice 2. Inicalion acapacidade utilirad da mochila, isto d Cap=b 3. Iniclaine o conjunte de itens contidos na mochila com vario, isto . tans=0 4 inicialize a soma das utilidades, isto e. soma ui = 0 5. Para int ate n as volume do item na ordern is Inserir them na ordern ina variavel liters Atualizar a capacidade disponie da mochila Cap=Cap volume do tem na andern I Atualizar a soma das utilidades da

alternativa para a obtenção da solução ótima através da resolução do problema de programação inteira e a aplicação da heurística gulosa é dada pelos seguintes passos:<br /><br />1. Ordenar os itens candidatos a serem colocados na mochila, de capacidade \(C\), em ordem decrescente de valor da utilidade.<br />2. Inicializar a capacidade utilizada da mochila, isto é, \(Cap = 0\).<br />3. Inicializar o conjunto de itens contidos na mochila com vazio, isto é, \(Items = \emptyset\).<br />4. Inicializar a soma das utilidades, isto é, soma \(Utilidade = 0\).<br />5. Para cada índice \(i\) até \(n\):<br /> - Se a capacidade disponível da mochila for maior ou igual ao volume do item na ordem \(i\), inserir o item na ordem \(i\) na variável \(Items\).<br /> - Atualizar a capacidade disponível da mochila: \(Cap = Cap - Volume\ do\ item\ na\ ordem\ i\).<br /> - Atualizar a soma das utilidades: \(Utilidade = Utilidade + Utilidade\ do\ item\ na\ ordem\ i\).<br /><br />Esse algoritmo corresponde à heurística gulosa para resolver o problema da mochila usando a programação inteira.