Re: Problema das Mochilas

["Marcos Romeiro Hryniewicz" <mr.h@uol.com.br>]

Oi Rubens,

O que quis dizer é q todos os objetos que forem colocados em uma mochila
(apenas 1 de cada ou nenhum) também serão colocadas na outra. É isso q está
escrito em:

Maximize sum(x(i)*p(i))

Subject to sum(x(i)*w(i,j)) <= C(j)

x(i) = 0 or 1

pois os mesmos x(i) (objetos) que estão no "Maximize" também estão no
"Subject to" multiplicados, respectivamente pelo seu valor e seu peso e no
caso do "Subject to", C(j) é o quanto cabe em cada mochila e w(i,j) é o peso
q o objeto i tem na mochila j. Para encontrar o valor ótimo de 141278
encontrado no arquivo, vc deve escolher uma soma de valores de objetos
maximizada para q a soma de seus pesos (que são diferentes para cada
mochila) caibam nas duas mochilas. Ou seja sum(x(i)*w(i,1)) <= 600 = C(1) e
sum(x(i)*w(i,2)) <= 600 = C(2). Note que os i's são os mesmos... Eu fiz
assim e deu certo para todos os exemplos do sac-94-suite e eu resolvi todos
só aceitando variáveis inteiras iguais a 0 ou 1. Espero q isso seja
suficiente para que o meu EP3 esteja correto. Minha dúvida é se quem não
está fazendo ED precisa resolver com todos os tipos de buscas mencionados,
pois só fiz com busca em largura. É preciso fazer as outras buscas Ernesto?

Espero ter ajudado.

[]s
Marcos

-----Mensagem Original-----
De: "Rubens Altimari" <rubens@bcc2000.net>
Para: <egbirgin-mac315@ime.usp.br>
Enviada em: domingo, 23 de junho de 2002 14:02
Assunto: Re: Problema das Mochilas


Oi, Marcos:

>http://www.aridolan.com/ga/gaa/KnapsackWeing1.html e de
acordo com ele, a soma dos pesos dos objetos deverá ser menor
ou igual do que a capacidade de cada uma das mochilas, como
se o ladrão roubasse os objetos com uma mochila e depois
tivesse que os passar para a outra.

Estou meio atrasado para comentar isto, mas não entendi o que você disse.
Fui no site que você indicou, e o que entendi é que os objetos têm pesos
diferentes para cada mochila. Ou seja, o ladrão teria de escolher não apenas
que objetos pegar, mas em que mochila colocar (pois daria um resultado difer
ente).

Porém, posso estar errado, ou então não entendi direito o que você escreveu.
Alguém tem algum comentário?

Rubens