Solução para o problema das Caixas e Livros

Problema retirado do teste 8 do professor Carlos Brito, da disciplina de Contrução e Análise de Algoritmos (CAnA).Problema:

Considere um conjunto com n livros, onde o i-esimo livro possui peso Pi < Kg. Os livros devem ser armazenados em caixas. Cada caixa pode receber até três livros e suporta um peso máximo de 1 Kg.

O problema consiste em armazenar todos os livros utilizando o menor número de caixas possível.

Suponha o algoritmo:

Enquanto existir livro sem caixa
Seleciione um subconjunto com até 3 livros e peso total máximo (mas <= 1 Kg), e colocar em uma nova caixa.

Pergunta-se, se o algoritmo está correto. Se sim, mostrar a prova de corretude. Se não, mostrar um contra exemplo e estimar a diferença entre a sua solução e a solução ótima, no pior caso.

Contra exemplo:
Sejam o livros com pesos, em gramas (503, 301, 502, 302, 501, 303).
O algoritmo vai preprerar a primeira caixa da seguinte maneira
C1 = (301, 302, 303) que nos dá a soma 906, que é a maior possível.

Agora nos restam os pesos (503, 502, 501). Então as caixas vão ficar
C2 = (503)
C3 = (502)
C4 = (501)
Ou seja, o algoritmo usou 4 caixas.

Porém existem uma outra organização que usa menos caixas:
C1 = (503,301)
C1 = (502,302)
C1 = (501,303)

Logo o algoritmo não é ótimo. A diferença entre a solução ótima e a solução encontrada pelo algoritmo para esse problema foi de 1 caixa.

Anúncios

Deixe um comentário »

RSS feed for comments on this post. TrackBack URI

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

Blog no WordPress.com.
Entries e comentários feeds.

%d blogueiros gostam disto: