DojoRio@Centro 20/03/2013 – Amigos, amigos, bagagens à parte

Olá, pessoas queridas. Tudo bem com vocês?

No dia 20 de março, fizemos um problema com características clássicas. Um grupo de amigos está planejando uma viagem e precisam decidir como dividirão as malas. Dado um conjunto de malas com um determinado peso e 2 carros, é possível dividir as malas para que todos os carros sempre carreguem o mesmo peso?

Um ponto que deve ser atentar  é que por mais que o peso possa ser divisível por 2 (temos 2 carros), nem sempre será possível dividir as malas por 2, já que as malas são inteiras. Por exemplo, 4 malas com pesos de 1, 2, 5, 4 – O peso total é 12, este peso é divisível por 2 carros e conseguimos arrumar as malas de forma que as malas de peso 2 e 4 fiquem num carro e as malas de peso 1 e 5 fiquem em outro. Agora suponha as mesmas 4 malas para serem divididas pelos mesmos 2 carros, só que com pesos diferentes de 1, 1, 1, 9 – por mais que 1 + 1 + 1 + 9 = 12 e 12 seja divisível por 2, a distribuição do peso não é possível, pois 3 < 9 e não podemos dividir a mala de peso 9 para que seu excedente em relação a metade do peso total das malas seja carregado em outro carro.

O desafio abordado é uma variação de um problema famoso, conhecido como Problema de Partição. Programação dinâmica é bastante utilizada para resolver problemas deste tipo.

A técnica da Programação Dinâmica possui algoritmos de resolução de alguns problemas, entre eles a Mochila. É possível visualizar esta variação do problema da partição como uma Mochila. Existem diversos tipos de mochilas e várias definições diferentes. Uma definição de um tipo de mochila (dada pela wikipedia) é:

“Dado um conjunto de artigos, cada um com um peso e um valor, determinar o número de cada item de incluir em um conjunto de modo que o peso total é inferior a ou igual a um determinado limite e o valor total é tão grande quanto possível. Ela deriva seu nome do problema enfrentado por alguém que está limitado por uma mochila de tamanho fixo e deve preenchê-la com os itens mais valiosos.”

A definição dada acima é para Mochilas  problemas de otimização: maximizar, minimizar, encontrar valores, etc. Outras Mochilas são aplicadas em problemas de decisão – retorna true ou false. Durante o dojo, este problema foi citado como pertencente à classe dos NP Completo.

A Mochila que estamos utilizando neste caso é de decisão, pois temos que decidir se é possível ou não dividir as malas de forma a igualar os pesos entre os carros.

As malas foram divididas por presenças ilustres e seus respectivos óculos. Um parabéns para o Luan e seus óculos gigantescos que roubaram a cena durante o dojo :). Decidimos bagagens com óculos dinâmicos com este código.

E as frases de efeito das bagagens que foram divididas com sucesso e foram para lugares maneiríssimos:

  • Problema ++++++
  • Novatos ++
  • Pessoas ++
  • Programação Dinâmica (PD) +++
  • Biscoito de castanhas (Padaria)
  • Explicação
  • Cissa Bel[é]m presente +
  • Retrospectiva
  • “Jac Abreu jornalista” (Jac anotando para o post do dojo)
  •  Ambiente legal
  • Recursão
  • Explicação bem detalhada (sobre o problema e sobre PD)
  • Não sou mias novato (desabafo do Júlio Marins 😛 )
  • Interatividade
  • Desenvolvimento de ideias
  • Retorno ao dojo +
  • Pessoas permanecendo no dojo
  • Problema acessível e ainda aplicando mochila (PD)
  • Pessoal empolgado 😀

As malas que ficaram em casa também tem o que dizer:

  • Thiago Be[e]m não veio ++
  • Otávio Cardoso não veio +
  • Flávio Amieiro não veio +
  • O dojo começou tarde +
  • Teclado com mofo =(
  • Pouca comida +++
  • Chegar atrasado ao dojo
  • Patota
  • Cadê a cadeira do “cabuuumm” 😛

Não importa o que acontecer, sempre terá dojo nas 4º feiras, começando em torno das 18:30 – 19:00 em algum lugar do Rio de Janeiro.

Gostou da gente? O dojo@Centro é realizado na Íparos – Av Treze de Maio, 13 – 6° andar – Cinelândia, entre 18:30 e 19:00 de todas as quartas feiras (menos feriados) . Qualquer dúvida, é só mandar email para o  grupo (google groups) do dojo, alguém do grupo sempre responde as dúvidas conforme for possível. Você é muito bem vindo 😀

Até a próxima :D

Anúncios

Os comentários estão desativados.

%d blogueiros gostam disto: