Programação Dinâmica - Maior arranjo de estantes

5

Estou tentando resolver um problema, por isso não estou procurando código, mas sim algoritmos semelhantes para que eu possa resolvê-lo sozinho.

Eu recebo n bookcases, cada um com uma quantidade de size de livros dentro. Vou mover algumas destas estantes para uma nova sala da seguinte forma:

  • A primeira estante de livros será sempre movida;
  • Vou manter a ordem das estantes na nova sala (não posso mudar de posição na nova sala);
  • A estante não pode ser colocada ao lado de qualquer uma das estantes de livros i-1 ou i+1 (ex: não posso colocar? -4-5 -? /? - 5-6 -? /? - 4-5 -6 -?);

Portanto, a estante 1 está sempre na nova sala. Além disso, se a estante de livros i estiver na sala, nem a i-1 nem a i+1 estarão na sala.

Qual configuração de estantes oferecerá a maior quantidade de livros?

Eu entendo que isso é resolvido usando um algoritmo de programação dinâmica, mas não tenho certeza qual deles. Eu inicialmente pensei que seria semelhante ao problema da mochila, mas eu não tenho um limite de livros, então é claramente diferente (pelo menos eu acho que é). A complexidade do alvo é O (n), mas qualquer ideia que me ajude vai fazer.

    
por Xzenon 15.03.2016 / 23:25
fonte

1 resposta

1

Esse problema é semelhante ao problema maior subsequência crescente . Digamos que armazenemos o número de livros dentro de cada estante de livros em uma matriz N.

N[i] = number of books in bookcase i.

Você mantém uma matriz S, onde S [i] é o valor máximo que você pode obter para a outra sala usando um subconjunto dos itens 1 a i que contém o item i.

S[ 1 ] = N[ 1 ]

S[ i ] = max( S[ 1 ], S[ 2 ], ... S[ i - 2 ] ) + N[ i ], for i = 3..N.Size

A resposta será então o valor max(S[N.Size], S[N.Size - 1]) . Para obter os itens reais que você pega, você pode manter informações adicionais em outra matriz PREV [i] - O item antes de eu na nova sala.

Isso é executado em O (n ^ 2) tempo, mas você pode melhorar isso para O (nlogn) usando árvores de intervalo ou indexadas binárias para obter o máximo em tempo logarítmico (semelhante ao maior problema de subsequência crescente)

Atualização: Apenas percebi que, se os valores forem positivos, podemos resolver isso em O (n)

S[i] =max(S[i-2], S[i-3]) + N[i]

Mas, se os valores puderem ser negativos, isso não funcionará

    
por 16.03.2016 / 12:30
fonte