Estrutura de Dados 1

Lista de Exercícios II ED I Data de entrega 20092024 As listas de exercícios são para serem resolvidas em duplas Cuidado com as cópias de trabalhos pois cópias surtirão na divisão de uma nota pela quantidade de trabalhos iguais As respostas aos problemas aqui tratados envolvem programação Sendo assim cada exercício é tratado como um programa diferente Somente os arquivosfonte devem ser enviados pelo SIGAA Para o envio é necessário se compactar TODOS os arquivos fontes construídos e então enviar este arquivo compactado pelo SIGAA Exercício 1 implemente o problema da Torre de Hanói A Torre de Hanói é composta de 3 hastes A B e C onde em uma haste encontramse discos dispostos como uma pirâmide todos de tamanhos diferentes onde um disco menor está sempre sobre um disco maior O problema é passar todos os discos da torre A para a torre C utilizando a torre B como auxiliar um disco por vez onde nenhum disco maior pode ficar em cima de um disco menor A seguir encontrase a Figura 1 que ilustra o problema Figura 1 Ilustração da Torre de Hanói Exercício 2 implemente um algoritmo que implemente um deque e controle a inserção e remoção de valores numéricos inteiros em um vetor de 10 valores Um menu deve ser construído com as opções de inserção e remoção que o usuário pode escolher para uma das 2 extremidades do vetor Após a execução de uma opção do menu o programa deve retornar para o menu principal para ser escolhida a próxima função a ser executada Segue as funcionalidades do programa Inserção no topo esta inserção muito parecida com a pilha deve ser realizada na frente dos valores já existentes no vetor caso ainda se tenha espaço Inserção no final assim como a fila a inserção deve ser realizada na última posição válida do vetor caso ainda se tenha espaço Remoção no topo esta opção remove o valor que está na cabeça do vetor caso ainda se tenha valores a serem removidos Remoção no final esta opção remove o valor que está no final do vetor caso ainda se tenham valores a serem removidos Verificar valor inicial o programa retorna ao usuário o valor que se encontra no início do vetor Verificar valor final o programa retorna ao usuário o valor que se encontra no final do vetor Fim o programa encerra sua execução Exercício 3 para um dado número inteiro 𝑛 1 o menor inteiro 𝑑 1 que divide 𝑛 é chamado de fator primo É possível determinar a fatoração prima de 𝑛 achandose o fator primo 𝑑 e substituindo 𝑛 pelo quociente 𝑛𝑑 repetindo essa operação até que 𝑛 seja igual a 1 Utilizando uma Pilha ou Fila implemente um programa que compute a fatoração prima de um número imprimindo os seus fatores em ordem crescente Por exemplo para 𝑛 3960 deverá ser impresso 11 5 3 3 2 2 2 Exercício 4 utilizando a estratégia de algoritmos gulosos ou de força bruta implemente os problemas a seguir na busca de uma solução possível não necessariamente a melhor Não necessariamente precisase utilizar a mesma estratégia de algoritmos gulosoforça bruta em todos os problemas Problema do Caixeiro Viajante o Este problema se baseia na realização de um percurso saindo de uma cidade passando por todas as outras e retornando na cidade inicial com o menor caminho a ser percorrido o Implemente para 100 cidades o Cada cidade terá sua coordenada 𝑥 𝑦 que deve ser inserida de forma automática e aleatória com limite de 1000 um mil por coordenada tentando evitar assim cidades com as MESMAS coordenadas 𝑥 𝑦 o Verificar a existência de cidades com coordenadas iguais o Devese tratar o problema como um grafo completo onde todas as cidades estão conectadas com todas as cidades o A distância entre 2 cidades diferentes deve ser calculada ou seja euclidiana 𝑑 𝑥1 𝑥22 𝑦1 𝑦22 Problema da Mochila o O usuário possui uma mochila que comporta uma certa quantidade de peso Existem diversos itens para serem escolhidos a serem incluídos na mochila onde cada item possui seu peso e seu valor O objetivo é se obter a mochila com o maior valor possível de itens o O peso da mochila o usuário pode estipular assim como a quantidade de itens o O peso e o valor de cada item devem ser construídos de forma automática e aleatória com um limite de 30 para cada característica do tem peso ou valor as quais não necessariamente devem ser iguais Projeto TEIA DO SABER 2005 Departamento de Matemática Estatística e Computação Secretaria de Estado da Educação SP UNESP Campus de Presidente Prudente Torres de Hanói Prof Dr José Ricardo R Zeni 1 TORRES DE HANÓI Jogo Educativo na mesa ou no computador Objetivo e Regras O jogo consiste de uma base onde estão firmadas três hastes verticais e um certo número de discos de diâmetros diferentes que se encaixam nas hastes Vamos chamar as três hastes de A origem B temporário e C destino Posição Inicial no começo do jogo os discos estão todos encaixados na haste A em ordem decrescente de tamanho com o maior disco embaixo e o menor disco acima de todos conforme ilustrado na figura abaixo esquerda para o caso de 5 discos Posição inicial para 5 discos Posição final para 5 discos O objetivo é mover todos os discos da haste A para a haste C obtendo a posição final mostrada na figura acima direita para o caso de 5 discos obedecendo às seguintes regras 1 Somente um disco pode ser movido por vez 2 Um disco maior nunca deve ser posto sobre um menor Simplificações Para facilitar a compreensão do jogo é conveniente fazer algumas simplificações reduzindo o número de discos A medida que o usuário adquirir habilidade com o jogo pode se aumentar a dificuldade aumentando o número de discos Para dois discos a solução é simples mova o disco menor para a haste temporária depois mova o maior para a haste de destino e finalmente mova o menor para a haste de destino Posição inicial 1º movimento 2º movimento 3º movimento Exercícios I 1 Resolva o jogo das torres de Hanói com 3 discos Descreva o seu raciocínio isto é a seqüência de movimentos para resolver o jogo Quantos movimentos foram realizados 2 Repita o problema acima para 4 discos e depois para 5 discos 3 Compare com os seus colegas o número de movimentos realizados para resolver o jogo das Torres de Hanói com 3 discos 4 discos e 5 discos Segundo Objetivo Otimização Um outro desafio que pode ser proposto é o seguinte realizar a tarefa de mover os discos da haste A para a haste C utilizando o menor número de movimentos possíveis Exercícios II 4 Qual o menor número de movimentos para resolver o jogo com 3 discos E com 4 discos 5 discos 5 Obtenha uma fórmula para o menor número de movimentos em função do número de discos Projeto TEIA DO SABER 2005 Departamento de Matemática Estatística e Computação Secretaria de Estado da Educação SP UNESP Campus de Presidente Prudente Torres de Hanói Prof Dr José Ricardo R Zeni 2 TORRES DE HANÓI RESPOSTAS E COMENTÁRIOS 1 2 e 3 As respostas dos exercícios 1 2 e 3 dependem do jogador A seqüência de movimentos e consequentemente o número de movimentos realizados depende do raciocínio utilizado O software na opção Simulação mostra a seqüência de movimentos para a solução ótima isto é a solução obtida com o menor número de movimentos para qualquer número de discos entre 1 e 8 Observação o software foi desenvolvido para o sistema operacional Windows 98 e tem apresentado problemas para a opção simulação está deixando rastros no Windows 2000 e Windows XP A opção Jogar tem funcionado bem independente do sistema operacional utilizado 4 A tabela abaixo fornece o menor número de movimentos em função do número de discos Discos 1 2 3 4 5 6 7 8 Movimentos 1 3 7 15 31 63 127 255 5 Notação Tn indica o menor número de movimentos necessários para mover n discos Tn 2 n 1 Histórico e Complexidade Computacional Conta a lenda que as torres de Hanói com 64 discos de ouro e três torres hastes de diamante foi um presente de Deus para os monges do Tibet que os incumbiu da tarefa de mover os 64 discos de uma haste para a outra segundo as regras do jogo Ainda de acordo com a lenda os monges foram alertados que quando acabassem de mover os discos aconteceria o fim dos tempos Para sorte da humanidade o problema tem uma complexidade exponencial em relação ao número de discos Para exemplificar se os monges fossem capaz de mover mil discos por segundo seria necessário cerca de 1 bilhão de anos quase a idade do universo estimada atualmente Método O jogo pode ser resolvido com o seguinte raciocínio recursivo para levar n discos da haste A para a haste C é necessário levar n1 discos de A para B depois deslocar o maior de A para C e em seguida levar os n1 discos de B para C A figura abaixo ilustra este raciocínio para o caso de 5 discos veja também as posições inicial e final na página 1 Objetivos e Regras Posição após a 1ª seqüência de movimentos Posição após o movimento do disco maior Observe que pelas regras do jogo não é permitido mover vários discos de uma só vez Assim para mover os n1 discos da haste A para a haste B é necessário usar a haste C como auxiliar seguindo o raciocínio anterior isto é é necessário levar antes os n2 discos de A para C e depois o próximo disco da haste A para a haste B e em seguida trazer os n2 discos de C para B Posição após mover os 3 discos menores Posição após mover o 2º disco maior Novamente para mover os n2 discos de A para C devese pensar recursivamente considerando n3 discos até chegarmos ao movimento de um disco que é trivial e assim podese iniciar os movimentos Projeto TEIA DO SABER 2005 Departamento de Matemática Estatística e Computação Secretaria de Estado da Educação SP UNESP Campus de Presidente Prudente Torres de Hanói Prof Dr José Ricardo R Zeni 3 TORRES DE HANÓI RECURSÃO Uma análise do método anterior nos mostra que Tn satisfaz a seguinte relação de recorrência linear de primeira ordem Tn 2Tn1 1 com valor inicial T1 1 Referências Campello Ruy E e Maculan Nelson Algoritmos e Heurísticas Desenvolvimento e Análise de Performance Capítulo 1 Editora Universidade Federal Fluminense 1994 Coutinho Severino C Números inteiros e Criptografia RSA Capítulo 5 Instituto de Matemática Pura e Aplicada IMPA 1997 Graham Ronald L Knuth Donald E e Patashnik Oren Matemática Concreta Capítulo 1 Editora Livro Técnico e Científico 2a edição 1995 Pícollo Homero L Estrutura de Dados Capítulo 4 MSD Software 2000 UNIVERSIDADE FEDERAL DO PARÁ BIBLIOTECA DE OBJETOS MATEMÁTICOS COORDENADOR Dr MARCIO LIMA TEXTO Torre de Hanói AUTORES Mayara Brito estagiária da BOM André Brito estagiário da BOM ORIENTADOR Dr Professor Márcio Lima coordenador da BOM 1 Torre de Hanói Você conhece ou já viu esse jogo Faz ideia de como jogar Gostaria de saber Então vamos conhecer a Torre de Hanói Torre de Hanói é um jogo criado pelo matemático francês Edouard Lucas em 1883O jogo também é conhecido por torre de bramanismo ou quebra cabeças do m do mundo O jogo consiste em uma base de madeira onde estão rmados três hastes verticais e um certo número de discos de madeira de diâmetros diferentes furados no centro Foi baseado em uma lenda Hindu a qual falava de um templo em Bena res cidade Santa da Índia onde existia uma torre sagrada do bramanismo cuja função era melhorar a disciplina mental dos jovens monges De acordo com a lenda no grande templo de Benares debaixo da cúpula que marca o centro do mundo há uma placa de bronze sobre a qual estão xadas três hastes de diamante Em uma dessas hastes o deus Brama no momento da criação do mundo colocou 64 discos de ouro puro de forma que o disco maior casse sobre a placa de bronze e os outros decrescendo até chegar ao topo A missão dada aos mongens foi que eles transferissem a torre de uma haste para a outra ultilizando a terceira como auxiliar seguindo as seguintes regras movendo apenas um disco por vezes e nunca colocar um disco maior em cima de um menor Os monges deveriam trabalhar com eciência noite e dia e quando terminassem o trabalho o templo seria transformado em pó e o mundo acabaria Como já foi dito o objetivo do jogo é passar a torre para uma haste di ferente ultilizando a outra como auxiliar obdecendo as duas regras Sendo assim surge uma pergunta chave qual o número mínimo de movimentos para realizar o jogo você saberia responder Antes de responder tal per gunta é necessário estudar o objeto então vamos lá 2 Para facilitar o entendimento e vericar que você realmente entendeu as regras do jogo vamos resolver a Torre de Hanói com um disco Observe Para resolver a Torre de Hanói com um disco é necessário apenas um movimento E com dois discos Veja a gura a baixo observe que são neces sário no mínimo três movimentos independente da haste que você escolha como sendo a haste nal Agora tente resolver uma torre de Hanói com três discos com o número mínimo de movimentos quantos movimentos serrão necessários veja na gura abaixo a solução para deslocar a torre para a haste do lado oposto e são necessários 7 movimentos no mínimo Agora que você já entendeu como resolver po jogo com um dois e três discos e sabe o número mínimo de movimentos de cada um mas é claro que não podemos car testando o número mínimo de jogadas para n discos então vamos começar a tirar algumas conclusões 3 Vamos conderar uma torre com n discos numerendo como 1 o menor disco e n o maior disco 1 2 3 n Para remover o disco n é preciso tirar todos de cima ou seja tirar todos os n1 discos que estão acima dele colocandoos em uma das hastes feito isso mova o disco n para a haste restante Agora mova de acordo com as regras os n 1 para a haste que se encontra o disco n Obeserve que você move os n 1 discos duas vezes e o disco n apenas uma De modo matemático seja βn o número mínimo de movimentos para resolver uma Torre de Hanói com n discos βn 1 é o número mínimo de movimentos para n 1 discos então temos βn βn 1 1 βn 1 βn 2βn 1 1 Como denimos βn sendo o número mínimo de movimento podemos vericar o seguinte β1 2β1 1 1 2 0 1 1 β2 2β2 1 1 2β1 1 2 1 1 3 β3 2β3 1 1 2β2 1 2 3 1 7 β4 2β4 1 1 2β3 1 2 7 1 15 β5 2β5 1 1 2β4 1 2 15 1 31 β6 2β6 1 1 2β5 1 2 31 1 63 Desse modo você pode descobrir o número mínimo de movimentos para n discos se souber o número de n 1 Mesmo assim ainda está complicado então observe o quadro a baixo 4 Analise bem o quadro e observe que Podemos notar então que o número somado é sempre o dobro do anterior que já havia sido somado ou seja de 1 para 3 foi somado dois e de 3 para 7 foi somado 4 22 e assim sucessivamente Outra observação importante é a relação entre o número de movimentos com a soma por exemplo do 1 para o 3 foi somado 2 e do 3 para o 7 foi somado 4 observe que é sempre somamos o sucessor do número em outras palavras temos que o resultado da quantidade mínima de movimentos é sempre 1 a menos do número que foi somado Veja o quadro a baixo Veja que o número somado é um número do tipo 2n e assim a sequência de números somados forma a PG 2 4 8 16 32 de razão q 2 Logo a quantidade mínima de movimentos é igual ao número somado menos 1 ou seja igual a 2n 1 Então descobrimos que βn 2n 1 5 Porém precisamos prova que a fórmula encontrada é válida já que ela foi dedusida através de alguns experimentos mas na matemática isso não é sucientemente necessário para dizer que a fórmula é válida precisa ser provado que a fómula vale para todo n número de discos Para provar a forma que deduzimos usaremos um processo chamado Indução Matemática ou Indução Finita Base de Indução Para n1 2n 1 21 1 2 1 1 o que está certo pelo nosso quadro anterior Hipótese de Indução Suponhamos que a fórmula 2n 1 é válida para algum n 1 Portanto βn 2n 1 Tese de Indução Usamos a Hipótese de Indução para provar que a fórmula também vale para n 1 Temos que βn 2βn 1 1 Ou equivalentemente βn 1 2βn 1 Pela Hipótese de Indução βn 1 22n 1 1 βn 1 2 2n 2 1 βn 1 2n1 1 Portanto pelo Princípio de Indução Finita βn 2n 1 para todo número n natural e maior que 1 Pronto a fórmula está provada e já sabemos que ela nos dá o número mínimo de movimentos para solucionar a Torre de Hanói 6 1 O problema da Torre de Hanói pode ser resolvido de forma recursiva A ideia básica é mover todos os discos da haste A para a haste C utilizando a haste B como auxiliar um disco por vez As regras são 1 Somente um disco pode ser movido por vez 2 Um disco maior nunca pode ser colocado sobre um disco menor Passos para a implementação A solução para o problema pode ser implementada com um algoritmo recur sivo onde Movemos os n 1 discos da haste A para a haste B Movemos o disco maior diretamente da haste A para a haste C Movemos os n 1 discos da haste B para a haste C utilizando a haste A como auxiliar Aqui está o código em Python para resolver o problema da Torre de Hanói def torredehanoin origem destino auxiliar if n 1 printfMova o disco 1 de origem para destino return Move n1 discos da origem para a haste auxiliar torredehanoin 1 origem auxiliar destino Move o disco n da origem para a haste destino printfMova o disco n de origem para destino Move os n1 discos da haste auxiliar para a haste destino torredehanoin 1 auxiliar destino origem Exemplo de uso n 3 Número de discos torredehanoin A C B 1 Explicação 1 Caso base Quando n 1 movemos o disco diretamente da origem para o destino 2 Recursão Para n 1 o algoritmo move os n 1 discos da origem para a haste auxiliar move o disco maior da origem para o destino e finalmente move os n 1 discos da auxiliar para o destino Saída esperada para n 3 Mova o disco 1 de A para C Mova o disco 2 de A para B Mova o disco 1 de C para B Mova o disco 3 de A para C Mova o disco 1 de B para A Mova o disco 2 de B para C Mova o disco 1 de A para C 2 Precisamos implementar um deque fila de dois extremos que permite in serção e remoção de valores em ambas as extremidades de um vetor com capacidade para 10 elementos Estrutura do Algoritmo O deque será implementado com um vetor de tamanho fixo 10 elementos e as seguintes operações serão permitidas 1 Inserção no topo Insere um elemento no início do deque semelhante a uma pilha 2 Inserção no final Insere um elemento no final do deque semelhante a uma fila 3 Remoção no topo Remove o primeiro elemento do deque 4 Remoção no final Remove o último elemento do deque 5 Verificar valor inicial Mostra o primeiro valor do deque 2 6 Verificar valor final Mostra o último valor do deque 7 Fim Termina o programa Aqui está o código em Python que implementa o deque com as funcio nalidades mencionadas class Deque def initself tamanho10 selfdeque None tamanho Inicializando o vetor com None selfinicio 1 selffim 1 selftamanho tamanho def estavazioself return selfinicio 1 def estacheioself return selffim 1 selftamanho selfinicio def inserirnotopoself valor if selfestacheio printDeque está cheio Não é possível inserir no topo return if selfestavazio selfinicio selffim 0 else selfinicio selfinicio 1 selftamanho selfdequeselfinicio valor printfValor valor inserido no topo def inserirnofinalself valor if selfestacheio printDeque está cheio Não é possível inserir no final return if selfestavazio selfinicio selffim 0 else selffim selffim 1 selftamanho selfdequeselffim valor printfValor valor inserido no final 3 def removerdotopoself if selfestavazio printDeque está vazio Não é possível remover do topo return printfValor selfdequeselfinicio removido do topo if selfinicio selffim selfinicio selffim 1 Deque está vazio agora else selfinicio selfinicio 1 selftamanho def removerdofinalself if selfestavazio printDeque está vazio Não é possível remover do final return printfValor selfdequeselffim removido do final if selfinicio selffim selfinicio selffim 1 Deque está vazio agora else selffim selffim 1 selftamanho selftamanho def verificarvalorinicialself if selfestavazio printDeque está vazio else printfValor inicial selfdequeselfinicio def verificarvalorfinalself if selfestavazio printDeque está vazio else printfValor final selfdequeselffim def menuself while True print Escolha uma operação print1 Inserir no topo print2 Inserir no final print3 Remover do topo print4 Remover do final 4 print5 Verificar valor inicial print6 Verificar valor final print7 Fim escolha intinputDigite o número da operação if escolha 1 valor intinputDigite o valor para inserir no topo selfinserirnotopovalor elif escolha 2 valor intinputDigite o valor para inserir no final selfinserirnofinalvalor elif escolha 3 selfremoverdotopo elif escolha 4 selfremoverdofinal elif escolha 5 selfverificarvalorinicial elif escolha 6 selfverificarvalorfinal elif escolha 7 printEncerrando o programa break else printOpção inválida Tente novamente Exemplo de uso deque Deque dequemenu Explicação 1 Classe Deque A classe contém todos os métodos necessários para realizar as operações no deque 2 Métodos de inserção e remoção Cada método verifica se o deque está cheio ou vazio antes de realizar a operação 3 Menu O menu interativo permite ao usuário escolher qual operação realizar no deque 4 Deque Circular O deque é implementado de forma circular para 5 garantir que o espaço seja usado eficientemente 3 O objetivo é implementar um programa que computa a fatoração prima de um número n utilizando uma pilha ou uma fila para armazenar os fatores e depois imprimilos em ordem crescente Estrutura do Algoritmo 1 Encontrar o menor divisor primo de n 2 Dividir n por esse divisor e repetir o processo até que n seja igual a 1 3 Utilizar uma estrutura de pilha ou fila para armazenar os divisores encontrados 4 Após terminar a fatoração imprimir os fatores em ordem crescente Código em Python Aqui está a implementação utilizando uma fila para armazenar os fatores from collections import deque def fatoracaopriman Inicializa a fila para armazenar os fatores primos fatores deque divisor 2 Enquanto n for maior que 1 continue dividindo pelos fatores primos while n 1 while n divisor 0 fatoresappenddivisor n n divisor divisor 1 return fatores 6 Função para imprimir os fatores em formato solicitado def imprimirfatoresfatores print joinmapstr fatores Exemplo de uso n intinputDigite um número inteiro para fatoração fatores fatoracaopriman imprimirfatoresfatores Explicação 1 Deque Utilizei a estrutura de dados deque da biblioteca collections para implementar a fila É eficiente tanto para inserções quanto para remoções nas extremidades 2 Divisão sucessiva Começamos com o divisor 2 o menor número primo e continuamos dividindo n enquanto ele for divisível por 2 Depois passamos para os próximos números primos 3 Inserção na fila A cada divisão bemsucedida inserimos o divisor na fila de fatores primos 4 Impressão dos fatores Após terminar a fatoração imprimimos os fatores em ordem crescente utilizando o método join para formatar a saída Exemplo de saída para n 3960 11 5 3 3 2 2 2 4 Problema do Caixeiro Viajante Vamos implementar um algoritmo para encontrar um percurso saindo de uma cidade passando por todas as outras e retornando à cidade inicial As cidades terão coordenadas aleatórias e devemos calcular a menor distância percorrida usando a fórmula da distância euclidiana 7 Implementação Caixeiro Viajante Aqui está a solução com base na descrição do enunciado gerando 100 cidades com coordenadas aleatórias import random import math import itertools Função para calcular a distância euclidiana entre duas cidades def distanciacidade1 cidade2 return mathsqrtcidade10 cidade202 cidade11 cidade212 Função que resolve o problema do Caixeiro Viajante utilizando força bruta def caixeiroviajantecidades numerocidades lencidades menordistancia floatinf melhorpercurso None Permutações de todas as ordens possíveis de visitas às cidades for percurso in itertoolspermutationsrangenumerocidades distanciatotal 0 for i in rangenumerocidades 1 distanciatotal distanciacidadespercursoi cidadespercursoi 1 distanciatotal distanciacidadespercurso1 cidadespercurso0 Retorna para a cidade inicial if distanciatotal menordistancia menordistancia distanciatotal melhorpercurso percurso return melhorpercurso menordistancia Função para gerar 100 cidades com coordenadas aleatórias def gerarcidadesnumerocidades limite1000 cidades while lencidades numerocidades cidade randomrandint0 limite randomrandint0 limite Verifica se a cidade já existe para evitar cidades com coordenadas iguais if cidade not in cidades cidadesappendcidade return cidades 8 Gera 100 cidades cidades gerarcidades100 Resolve o problema do caixeiro viajante melhorpercurso menordistancia caixeiroviajantecidades printMelhor percurso melhorpercurso printMenor distância menordistancia Explicação 1 Gerar cidades A função gerarcidades cria 100 cidades com coor denadas aleatórias no intervalo de 0 a 1000 A função também evita coordenadas duplicadas 2 Distância Euclidiana Utilizamos a fórmula da distância euclidiana para calcular a distância entre duas cidades 3 Permutações A função itertoolspermutations gera todas as pos síveis ordens de visita às cidades 4 Menor caminho O algoritmo força bruta percorre todas as permu tações para encontrar o percurso com a menor distância Limitação Este algoritmo é de força bruta portanto seu desempenho será insuficiente para um número tão grande de cidades 100 mas ele é adequado para ilustrar o conceito Problema da Mochila Agora vamos implementar a solução do problema da mochila usando um algoritmo guloso onde o objetivo é maximizar o valor dos itens escolhidos sem exceder o peso máximo Implementação Problema da Mochila Aqui está o código para resolver o problema da mochila 9 import random Função que resolve o problema da Mochila usando um algoritmo guloso def mochilapesomaximo itens Ordena os itens pela razão valorpeso itensordenados sorteditens keylambda x x1 x0 reverseTrue pesoatual 0 valortotal 0 mochilaitens for peso valor in itensordenados if pesoatual peso pesomaximo mochilaitensappendpeso valor pesoatual peso valortotal valor return mochilaitens valortotal Função para gerar itens com peso e valor aleatórios def geraritensnumeroitens limitepeso30 limitevalor30 return randomrandint1 limitepeso randomrandint1 limitevalor for in rangenumeroitens Define o peso máximo da mochila e gera itens aleatórios pesomaximo 100 itens geraritens20 Resolve o problema da mochila mochilaitens valortotal mochilapesomaximo itens printItens na mochila mochilaitens printValor total valortotal Explicação 1 Gerar itens A função geraritens cria uma lista de 20 itens com pesos e valores gerados aleatoriamente no intervalo de 1 a 30 2 Algoritmo guloso Ordenamos os itens pela razão valorpeso e adi cionamos itens à mochila até atingir o peso máximo 3 Resultado O algoritmo devolve os itens escolhidos e o valor total 10