Algoritmo do acampamento de treinamento

Question

Algoritmo do acampamento de treinamento

#1 resposta do (2 votos)
#2 resposta do (1 votos)

5

Descrição do problema -

A tarefa é encontrar o segmento contíguo de testes mais lucrativo, dada uma sequência de pontuações de testes, sendo permitido abandonar qualquer teste k de um intervalo escolhido.

O problema parece ser um problema de DP no início, mas a complexidade surge quando a condição de queda de teste entra em cena.

Quais modificações podem ser feitas na abordagem clássica de DP para esse problema? Ou existe uma abordagem completamente diferente?

Faixa de teste - N < = 10 ⁴

Fonte - INOI 2011 Q Paper

algorithms dynamic-programming

por 7Aces 24.12.2012 / 14:40

fonte

2 respostas

Tags algorithms dynamic-programming

Como devo organizar bugs em redmine? Existe alguma maneira profissional de ilustrar a diferença entre dois diagramas?

score 2 · Answer 1

Bem, aqui como eu faria isso (sem entrar em muitos detalhes)

Gostaria de acompanhar o valor de todos os resultados que descartei. Eu provavelmente os colocaria em uma fila ordenada cujo tamanho é o número permitido de teste descartado. Ele seria classificado como o teste de queda, o mais próximo de zero é no início. Ao percorrer a lista com o algoritmo tradicional, faria o seguinte:

if I encounter a negative number
    if the queue is not full
        add it to the queue
    else
        if the new negative number is smaller (farther from zero) than the first number in the queue
            remove the first number from the queue
            add the new number to the queue
            add the removed number to the current subsequence value
        else
            add the new negative number to the current subsequence value

Dessa forma, você sempre mantém a subsequência sem a pior marca da sequência, e se você encontrar uma marca ainda pior, você pode restaurar o valor de uma marca anteriormente descartada para o valor da sua subsequência.

score 1 · Answer 2

O algoritmo original é basicamente:

for each position:
    calculate best range ending at this position
print best over all possible ending positions

O melhor intervalo possível que termina em uma posição é o máximo de:

0 (começando do zero aqui)
o melhor intervalo possível da posição anterior + nova marca

Agora, precisamos calcular os finais K, para diferentes quantidades de testes descartados

for each position:
    for k = 0 to K:
        calculate best possible range ending at this position and dropping at most k tests
print best of all calculated ranges

O melhor intervalo possível é o máximo de:

0 (iniciando um novo intervalo nesta posição)
o melhor intervalo possível da posição anterior + nova marca
o melhor intervalo possível da posição anterior e um teste a menos