Procurando por um algoritmo DP para um problema específico de embalagem

5

Eu tenho o seguinte problema para resolver:

Dado um ferry com comprimento d e uma lista de n carros com seu comprimento, devemos carregar os carros no ferry em uma ordem em que eles aparecem na lista em 2 pistas diferentes (cada uma com comprimento d). Escreva um programa que, com o comprimento d, a lista de carros produza o número máximo de carros que podem ser carregados na balsa.

É muito fácil de fazer em O (2 ^ carros) com retrocesso - carregamos o carro à esquerda e tentamos todas as possibilidades, economizamos o máximo e carregamos o carro à direita e fazemos o mesmo salvamento máximo novamente.

Mas tenho a sensação de que isso pode ser reduzido a tempo polinomial com programação dinâmica. Como saber se minha intuição é verdadeira?

    
por qiubit 20.01.2015 / 20:31
fonte

2 respostas

3

Uma possível abordagem é a seguinte.

Eu vou fazer as seguintes suposições. Deixe-me saber se algum deles está realmente incorreto. Assim que encontrarmos um carro que possa ser adicionado em nenhuma das faixas, paramos de adicionar carros à balsa (não é permitido pular um carro grande para adicionar um carro menor que aparece na lista). Eu vou fazer a suposição de que a soma do comprimento de todos os carros está abaixo de 2d. Se não for o caso, isso pode ser facilmente aplicado em uma etapa de pré-processamento. Eu também vou considerar que d é um valor inteiro, assim como todos os tamanhos de carros.

O que vamos fazer agora é resolver um problema da mochila 0/1 para descobrir se um conjunto de carros pode caber em ambas as pistas.

Aqui o tamanho da mochila é d (na verdade é uma pista), o tamanho dos itens é o tamanho dos carros e o valor associado aos itens é o tamanho dos carros (ou seja, queremos preencher uma pista, tanto quanto possível). Para resolver este problema de mochila 0/1, você pode usar o algoritmo DP descrito na seguinte página da wikipedia: link ( Vou apenas reproduzi-lo aqui para que a resposta apareça mesmo se a página da Wikipedia desaparecer:)

Vamos chamar s1, o tamanho do carro 1, s2 o tamanho do carro2 e assim por diante (vamos considerar que temos n carros).

Defina m [i, s] como o valor máximo que pode ser obtido com um tamanho total usado menor ou igual a s usando carros até i (primeiros carros).

Podemos definir m [i, s] recursivamente da seguinte forma: m [i, s] = m [i-1, s] se si > s \, (o novo carro é maior que o limite de tamanho atual) m [i, s] = max (m [i-1, s], \, m [i-1, s-si] + si) se si menor ou igual a s.

A solução pode então ser encontrada calculando m [n, d].

vamos chamar s, a soma do comprimento dos carros na solução do problema da mochila. Se a soma de todos os comprimentos de carros for menor ou igual a d, então todos os carros considerados para resolver os problemas da mochila podem caber na balsa (sendo uma pista todas as selecionadas para fazer parte da solução da mochila, a outra pista sendo o resto). Se a soma do comprimento do resto dos carros for mais que d, então todos os carros não caberão na balsa. Remova o último carro da lista dos carros e resolva novamente o problema da mochila. Faça isso até que a soma do comprimento dos carros não selecionados esteja abaixo de d.

A complexidade do algoritmo DP para resolver o problema da mochila é O (nd) e precisa ser resolvida no máximo n vezes - > complexidade O (n ^ 2d)

Aqui está um esboço da solução em python:

def solveKnapsack(cars, lengthOfLane):
  m = [[0] * (lengthOfLane+1)]
  for s in cars:
    m.append([])
    for j in range(lengthOfLane+1):
      if s <= j:
        m[-1].append(max(m[-2][j],m[-2][j-s]+s))
      else:
        m[-1].append(m[-2][j])
  return max(m[-1])

def solveTwoLanes(cars, lengthOfLane):
  maxOneLane = solveKnapsack(cars, lengthOfLane)
  if sum(cars) - maxOneLane <= lengthOfLane:
    return len(cars)
  else:
    return solveTwoLanes(cars[:-1], lengthOfLane)


def main():
  # small example that should output 2.
  print solveTwoLanes([3,3,3,1],5)

if  __name__ =='__main__':main()
    
por 26.01.2015 / 17:47
fonte
0

Este é um problema de mochila múltipla. Resolvendo os algoritmos Meet-in-the-middle, é preciso O (2 ^ (n / 2)) para cada "pista".

partition the set {1...n} into two sets A and B of approximately equal size
compute the weights and values of all subsets of each set for each subset of A

find the subset of B of greatest value such that the combined weight is less than W
keep track of the greatest combined value seen so far

Mais detalhes aqui: link

    
por 28.01.2015 / 15:01
fonte