Ir para o conteúdo
epolozero

Problema das ONI

Mensagens Recomendadas

epolozero    14
epolozero

Boas, estou a tentar resolver um problema ( http://www.dcc.fc.up.pt/oni/problemas/2014/qualificacao/probC.html ) mas estou com algumas dificuldades em como resolve-lo.

O Problema

Dado um conjunto de N casas dispostas numa linha e identificadas por coordenadas inteiras, a tua tarefa é calcular qual o percurso que minimiza a soma dos tempo de entrega, isto é, qual a ordem em que as casas devem ser visitadas de modo a que a soma do tempo que a lambreta demora a chegar a cada uma delas é a menor possível.

A ideia do meu algoritmo é pegar no ponto de partida (i_centro) e descobrir se é melhor ir pela direita ou pela esquerda.

Queria só que me dissesem se é assim que se resolve o problema, existe algum método que possa aplicar, se devo resolver outros problemas mais fáceis sobre um determinado método, para depois aplicá-lo neste mais difícil...

def best(i_esquerda, i_centro, i_direita, inicio=False):
  #se todas as casas tiverem sido visitadas
  if i_esquerda < 0 and i_direita > n-1:
  return 0
  #se todas as casas da esquerda tiverem sido visitadas, visita as casas da direita
  if i_esquerda < 0:
  return best(i_esquerda, i_direita, i_direita + 1) + abs(direita[i_centro] - esquerda[i_esquerda])
  #se todas as casas da direita tiverem sido visitadas, visita as casas da esquerda
  if i_direita > n-1:
  return best(i_esquerda -1, i_direita, i_direita) + abs( esquerda[i_centro] - direita[i_direita])
  else:
  if inicio:
	 inicio = False
	 return min(best(i_esquerda - 1, i_esquerda, i_direita) + abs(esquerda[i_esquerda]),
			  best(i_direita +1, i_direita, i_direita) + abs(direita[i_direita]))
  else: #visita as casas da esquerda e da direita e devolve a melhor
	 return min(best(i_esquerda - 1, i_esquerda, i_direita) + abs( esquerda[i_centro] - direita[i_direita]),
			  best(i_direita + 1, i_direita, i_direita) + abs(direita[i_centro] - esquerda[i_esquerda]))	  



esquerda = [-4, -1]
direita = [4, 5, 6]
n=5
best(1, 0, 0, True)

Editado por epolozero

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
epolozero    14
epolozero

já emendei alguns erros, mas a resposta continua a não ser a correta.

def best_path(i_esquerda, i_direita, valor_anterior):

  #se ja tiver visitado todas as casas
  if i_direita == len(direita) - 1 and i_esquerda == len(esquerda) - 1:
  return 0

  #se ja tiver visitado todas as casas da direita, visita as casas da esquerda
  if i_direita == len(direita) - 1:
  return best_path(i_esquerda + 1, i_direita, esquerda[i_esquerda]) + abs(valor_anterior - esquerda[i_esquerda])		


  #se ja tiver visitado todas as casas da esquerda, visita as casas da direita
  if i_esquerda == len(esquerda) - 1:
  return best_path(i_esquerda, i_direita + 1, direita[i_direita])   + abs(valor_anterior - direita[i_direita])



  # melhor ir pela direita ou pela esquerda  
  else:  
  return min( best_path(i_esquerda + 1, i_direita, esquerda[i_esquerda]) + abs(valor_anterior - esquerda[i_esquerda]),  #esquerda
		    best_path(i_esquerda, i_direita + 1, direita[i_direita])   + abs(valor_anterior - direita[i_direita]))   #direita





direita = [4, 5, 6]
esquerda = [-4, -1]
print best_path(0, 0, 0)

Editado por epolozero

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
epolozero    14
epolozero

Consegui!! hehehe

Fica aqui o código, deixem dicas em como melhora-lo,

def calcula(valor_atual, i_esquerda, i_direita, total):
  #se as casas tiverem sido todas visitadas
  if i_esquerda == len(esquerda) and i_direita == len(direita):
  return 0

  #se as casas da esquerda tiverem sido todas visitadas, visita as casas da direita
  if i_esquerda == len(esquerda):
  return calcula(direita[i_direita], i_esquerda, i_direita+1, abs(valor_atual - direita[i_direita])+total) +
						 total+ abs(valor_atual - direita[i_direita])

  #se as casas da direita tiverem sido todas visitadas, visita as casas da esquerda
  if i_direita == len(direita):
  return calcula(esquerda[i_esquerda], i_esquerda+1, i_direita, abs(valor_atual - esquerda[i_esquerda])+total) +
						total+abs(valor_atual - esquerda[i_esquerda])
  #se as houverem casas da esquerda e da direita por visirar, visita as da esquerda e direita e retorna o melhor resultado
  else:
  return min(calcula(esquerda[i_esquerda], i_esquerda+1, i_direita,  abs(valor_atual - esquerda[i_esquerda])+total) +
				   total+ abs(valor_atual - esquerda[i_esquerda]),	 #esquerda

				  calcula(direita[i_direita], i_esquerda, i_direita+1, abs(valor_atual - direita[i_direita])+total) +
					    total+abs(valor_atual - direita[i_direita]))		  #direita



total = 0
esquerda = [-2]
direita = [1,2]	
print calcula(0, 0, 0,0)

Editado por epolozero

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
epolozero    14
epolozero

Deu-te quantos pontos?

Deu-me 60 pontos, vou tentar aplicar DP para ver se consigo 100 pontos.

Fica aqui o codigo que submeti em pascal(não dá para submeter em python)

Program pizza;
var total,i,aux,j,aux1,aux2,n:integer;
   direita : array[0..3500] of longint;
   esquerda:array[0..3500]of longint;
   tamanho_esquerda,tamanho_direita:longint;

function min(a:longint;b:longint):longint;
begin
  if a>b then
  min:=b
  else
  min:=a;
end;

function calcula(valor_atual:longint; i_esquerda:longint; i_direita:longint; total:longint): longint;
begin
  if (i_esquerda = -1) and (i_direita = tamanho_direita) then
  begin
  calcula:=0;
  exit;
  end;  
  if i_esquerda = -1 then
  begin
  calcula:= calcula(direita[i_direita], i_esquerda, i_direita+1, abs(valor_atual - direita[i_direita])+total) +total+ abs(valor_atual - direita[i_direita])  ;
  exit;
  end;  

  if i_direita = tamanho_direita then
  begin
  calcula:=calcula(esquerda[i_esquerda], i_esquerda-1, i_direita, abs(valor_atual - esquerda[i_esquerda])+total) + total+abs(valor_atual - esquerda[i_esquerda]);
  exit;
   end 
  else
  calcula:= min(calcula(esquerda[i_esquerda], i_esquerda-1, i_direita,  abs(valor_atual - esquerda[i_esquerda])+total) +total+ abs(valor_atual - esquerda[i_esquerda]), 
			    calcula(direita[i_direita], i_esquerda, i_direita+1, abs(valor_atual - direita[i_direita])+total) + total+abs(valor_atual - direita[i_direita]))



end;

begin

readln(n);
aux1:=0;
aux2:=0;
tamanho_direita:=0;
tamanho_esquerda:=0;

for i:=1 to n do
begin
  readln(aux);
  if aux<0 then
  begin
  tamanho_esquerda:= tamanho_esquerda + 1;
  esquerda[aux1]:=aux;
  aux1:=aux1+1;
  end
  else
  begin
  tamanho_direita:=tamanho_direita+1;
  direita[aux2]:=aux;
  aux2:=aux2+1;
  end;
end;

writeln(calcula(0, tamanho_esquerda-1,0,0));

end.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade