Como é resolvido o “problema da colheita de pizza‍” usando técnicas de programação dinâmica?

9

Problema de escolha de pizza de Winkler:

  • Uma pizza circular de nfatias de pizza , onde a fatia item área S_i, ou seja, a área é diferente para cada pedaço de pizza.
  • Comedores Alice e Bob se revezam escolhendo fatias, mas é rude criar várias lacunas na torta (considere isso não permitido).
    • Assim, cada comedor é restrito a tomar uma das duas fatias adjacentes à região aberta. Alice vai primeiro, e os dois comedores buscam o máximo de torta possível.

Como um algoritmo de programação dinâmica determinaria a quantidade de torta que Alice come, se Alice e Bob jogam perfeitamente para maximizar seu consumo de pizza?

Meu entendimento:

Em um problema geral de DP, avançamos na busca de subproblemas que podem ser visualizados usando a árvore de recursão ou, mais precisamente, usando um DAG. Aqui, não estou encontrando nenhuma pista para encontrar os subproblemas aqui.

Aqui, para um determinado conjunto de S_i s, precisamos maximizar a área de fatias comidas por Alice. Isso dependerá da escolha de uma permutação de fatias de pizza dentre (n-1) permutações. A escolha de uma fatia máxima da área dentre duas opções disponíveis a cada n \ 2 turnos que Alice obtém nos fornecerá a área total da fatia para uma permutação. Precisamos encontrar a área da fatia para todas essas permutações. E então o máximo disso.

Alguém pode me ajudar em como avançar?

algorithms dynamic-programming Amit Shekhar
fonte

Respostas:

5

Comece considerando as fatias colocadas em uma fileira e você pode escolher uma das duas extremidades. Nesse caso, supondo que seja a sua vez de escolher, fica claro que pizzaAmount(slices)é

  1. Se não sobrar pizza, o resultado é 0
  2. Se houver apenas um resultado de fatia, essa fatia
  3. Se houver pelo menos duas fatias, o resultado será:

(usando sintaxe Python)

max(slices[0] + sum(slices[1:]) - pizzaAmount(slices[1:]),
    slices[-1] + sum(slices[:-1]) - pizzaAmount(slices[:-1]))

em outras palavras, você deve considerar as duas alternativas e, depois de tomar sua fatia, receberá toda a pizza restante, exceto o resultado da chamada recursiva (porque seu amigo usará a mesma estratégia).

Você pode implementar isso com DP (ou memoizing) porque a matriz é realmente fixa e você pode apenas considerar como parâmetros o primeiro e o último índice de fatia.

Para resolver o problema completo original, basta tentar todas as fatias como fatia inicial e escolher a que maximiza o resultado.

6502
fonte
Obrigado "6502". Eu posso visualizar melhor o problema utilizando a dica de "considerar as fatias colocadas em uma fileira e escolher uma das duas extremidades". Dada a relação de recorrência, é também cuidar da escolha ideal do oponente. Vou postar um algoritmo formal em breve. Obrigado rapazes!!
Apenas curioso, qual é a ordem da complexidade para esse algoritmo? 0 (n * 2 ^ n)?
@ Akron: Isto é o que seria sem uma abordagem de programação dinâmica ou memorização. No entanto, você pode tirar proveito do fato de que o resultado de pizzaAmountdepende apenas do índice inicial e final das fatias restantes e não da sequência de quais fatias de pizza você e seu amigo já comeram, para que você possa armazenar o resultado em um matriz para evitar recomputação. A ordem do algoritmo é, portanto, O (n ** 2).
6502
Se alguém ainda está lutando para entender, este link tem uma explicação muito boa.
Amit Shekhar
3

Para parte da pizza, defina F(i,j)como máximo o quanto a pessoa que escolhe primeiro a fatia pode comer. Fatias de parte da pizza (i,j)são:

if i <= j than slices i, i+1, ..., j-1, j
if i > j than slices i, i+1, ..., n-1, n, 1, 2, ..., j-1, j
and we don't define it for whole pizza, abs(i-j) < n-1

Defina R(i,j)(quanto resta para a segunda pessoa) como sum(S_x, x in slices(i,j)) - F(i,j).

Com:

F(i,i) = S_i,
F(i,j) = max( S_i + R(i+1,j), S_j + R(i,j-1) ),

o máximo que Alice pode comer é calculado por:

max( S_i + F(i+1, (i-1) if i > 1 else n) ).
Ante
fonte