Como dividir consecutivamente uma pilha a fim de maximizar a soma do produto do número de elementos de cada parte da pilha?

Question

Considere que você tenha n peças empilhadas e você pode dividi-las em duas pilhas menores do tamanho que você desejar. Toda vez que você divide uma pilha, você faz o produto do número de peças das duas pilhas menores. Repita esse procedimento até que todas as pilhas tenha tamanho unitário. Nesse momento some todos os produtos encontrados anteriormente. Como dividir as pilhas de forma que a soma final seja máxima? Como o resultado muda se ao invés de você fazer o produto, você fizer a soma?

Answer 1

No caso em que queremos maximizar a soma do produto do número de elementos, o código abaixo representa uma implementação simples usando python que gera todas divisões possíveis que permitem a maximização. Como pode-se verificar escolhendo arbitrariamente um n, quaisquer divisões geram a mesma soma.

def maxSumProd(n,results={}): # n é o número de elementos da pilha original
    if n==1:
        return 0
    if n==2:
        return 1
    else:
        maxSum=0
        for i in range(1,int(n/2)+1):
            if n-i not in results:
                results[n-i]=maxSumProd(n-i)
            if i not in results:
                results[i]=maxSumProd(i)
            if (n-i)*i+results[n-i]+results[i]>=maxSum:
                maxSum=(n-i)*i+results[n-i]+results[i]
                print 'n','=',n,':',i,n-i
        return maxSum

if __name__ == '__main__':
    n=6
    maxSumProd(n)

De forma análoga, geramos as divisões para a maximização da soma da soma dos elementos com o código abaixo. Nesse caso, a maximização é feita dividindo-se a pilha sempre em duas pilhas com 1 e n-1 elementos em cada.

def maxSumSum(n,results={}): # n é o número de elementos da pilha original
    if n==1:
        return 0
    if n==2:
        return 2
    else:
        maxSum=0
        for i in range(1,int(n/2)+1):
            if n-i not in results:
                results[n-i]=maxSumSum(n-i)
            if i not in results:
                results[i]=maxSumSum(i)    
            if (n-i)+i+results[n-i]+results[i]>=maxSum:
                maxSum=(n-i)+i+results[n-i]+results[i]
                print 'n','=',n,':',i,n-i
        return maxSum

if __name__ == '__main__':
    n=6
    maxSumSum(n)