Minha solução de força bruta é muito lenta, precisava da solução de DP [fechada]

5

Definição de problema conciso:

given n and {a,b,c}; 
(1 ≤ n, a, b, c ≤ 4000);
Constraint -> a*i + b*j + c*k==n (i,j,k>=0);
Objective-> maximize(i,j,k)

Exemplos:

n=47 and a=7,b=5,c=8 -> max=9 (i=1,j=8,k=0) == 7*1+5*8+8*0=47
n=7 and a=5,b=5,c=2  -> max=2 (i=1,j=0,k=1) or (i=0,j=1,k=1) 

Minha primeira solução é apenas força bruta e dá "TIME_LIMIT_EXCEEDED" para algumas entradas como {4000 e 1,2,3}. Eu acho que esse problema pode ser resolvido usando DP , mas eu não consigo descobrir. Eu ficaria muito grato se alguém fornecesse a maneira de construir a solução de DP a partir deste problema. ( A principal coisa que eu quero não é apenas uma solução, mas eu quero um bom entendimento de como construir soluções de DP ). Abaixo está a minha solução:

#include <iostream>
using namespace std;

int main() {
    int n,a,b,c;
    cin>>n>>a>>b>>c;
    int max=0;

    for (int i=0;i<=n/a;i++) { 
        for (int j=0;j<=n/b;j++) { 
            for (int k=0;k<=n/c;k++) { 

                if ((a*i+b*j+c*k)==n) {
                    if (max<i+j+k) {
                        max = i+j+k;
                    }
                }

            }
        }
    }
    cout<<max;
    return 0;
}
    
por Humoyun 27.04.2016 / 15:14
fonte

5 respostas

1

O OP comentou em um comentário que achou o problema marcado como "força bruta e DP". O que é absolutamente ridículo. Aqui está a solução de tempo linear:

  1. Observe que a ordem de a, b, c é bastante irrelevante, então ordene-os para fazer um ≥ b ≥ c.

  2. Calcule g = gcd (a, b, c) (máximo divisor comum). Se n não é divisível por g, então não há solução. Caso contrário, divida a, b, c e n por g. Agora mdc (a, b, c) = 1.

  3. Calcule g = gcd (b, c), o que significa que n - ai deve ser um múltiplo de g. Encontre i0 = o menor i tal que n - ai é um múltiplo de g. Esse i existe porque gcd (a, g) = 1. Valores possíveis para i que podem levar a soluções são i0, i0 + g, i0 + 2g e assim por diante. Se n - a * i0 < 0 então não há solução.

  4. Divida b e c por g. Agora temos que encontrar j, k que resolvam (n - ai) / g = bj + ck, para i = i0, i0 + g, i0 + 2g e assim por diante. gcd (b, c) é agora 1. Para cada um desses i, seja m = (n - ai) / g, então precisamos de bj modulo c = m modulo c. Como o mdc (b, c) = 1, há um menor j0 ≥ 0 resolvendo esta equação. Os outros valores que resolvem isso seriam j0 + c, j0 + 2c, j + 3c. No entanto, toda vez que aumentamos j por c, precisamos diminuir k por b e, como b ≥ c, isso não pode melhorar a solução. Temos k = (m - b * j0) / c, e este k deve ser ≥ 0. O aumento de j não pode fazer k ≥ 0 se for menor que 0 para um j menor. Isto significa que para um determinado i, escolhemos j = menor j tal que bj modulo c = m modulo c, e k = (m - b * j0) / c.

  5. Para encontrar j0 rapidamente, criamos uma tabela de pesquisa T mapeando um valor de módulo m para o menor j com bj módulo c = m. Isto é feito em tempo linear calculando b * 0 módulo c, b * 1 módulo c etc. e definindo T [b * t módulo c] = t para 0 ≤ t < c.

  6. O algoritmo começa agora com i = i0 e nenhuma solução encontrada até o momento. Se n - ai < 0 então retorne com a melhor solução encontrada até o momento. Caso contrário, deixe m = (n - ai) / g. Seja j = T [m modulo c], k = (m - b * j) / c. Se k ≥ 0 e i + j + k é melhor do que a melhor solução até então, encontramos uma nova melhor solução. Caso contrário continue com i substituído por i + g.

  7. Aceleramos o algoritmo observando que, após calcular m, sabemos que i + j + k ≤ i + m / c, que nunca está aumentando. Portanto, se encontrarmos uma solução e i + m / c não for maior que essa solução, poderemos sair do algoritmo porque sabemos que encontramos uma solução que não pode ser melhorada ainda mais.

Com a entrada n = 4000, a, b, c = 1, 2, 3: rearranjamos a = 3, b = 2, c = 1. mdc (a, b, c) = 1 assim, a, b , c, n permanecem inalterados. g = gcd (b, c) = 1, então b, c não são alterados, a tabela T contém um valor T [0] = 0.

Deixamos i = 0, e n - ai é divisível por g = 1. Então começamos com i = 0, m = 4000, j = T [0] = 0, k = (4000 - j * b) / c = 4000, dando a solução i = 0, j = 0, k = 4000.

A seguir deixamos i = 1, m = 3997. i + m / c = 3998 < 4000, então a solução que encontramos anteriormente é ótima. Então o problema que excedeu o limite de tempo é tão simples que eu posso escrever o cálculo completo. (BTW se c = 1 após dividir a, b, c, n pelo mdc (a, b, c), então i = 0, j = 0, k = n, é sempre a solução ótima).

Eu acho que a solução pode ser sub-linear no tempo se acharmos mais rápido O (g) usando o algoritmo de Euclides, e em vez de construir uma tabela T em O (c) encontrar os valores j usando o algoritmo de Euclides, esperando Podemos provar que rapidamente uma solução encontrada é ótima.

    
por 30.04.2016 / 21:45
fonte
6

Pegue o terceiro loop: é absolutamente desnecessário. Você verifica se (a * i + b * j + c * k) == n. Isso significa que k deve ser igual a (n - a * i - b * j) / c. Então, uma mudança trivial é apenas calcular esse k e verificar se é uma solução.

Ordene a, b, c tal que a ≥ b ≥ c. Agora é óbvio que, à medida que j cresce, k deve encolher tanto ou mais, então a soma j + k não pode crescer. Isso significa que se você encontrar um valor para k dado i e j, você não precisa se preocupar em verificar qualquer j maior. A soma i + j + k não aumentará.

Em seguida, olharei o algoritmo Euclids para encontrar soluções de bj + ck = n - ai. E, finalmente, você pode estimar quão grande i + j + k pode se tornar à medida que se torna maior. Novamente, a soma tenderá a ficar menor se eu ficar maior, e quando eu for grande o suficiente, você será capaz de provar que a soma não pode aumentar mais.

    
por 27.04.2016 / 21:30
fonte
1

Eu acho que no caso o 'conjunto de problemas menores' será:

  • maximiza (i, j, k) para n - x onde x é um número que é mais difícil computar

fora do topo da minha cabeça, eu calcularia:

n mod a, n mod b, n mod c

dando-me um conjunto de x para o qual eu posso facilmente maximizar o efeito de corrosão i, j ou k ie.

(n - (n mod a)) / i etc.

e armazene-os junto com o restante, x em uma estrutura de árvore

Em seguida, para cada resultado, calcule:

(n mod a) mod b, (n mod a) mod c etc

armazenando novamente o restante e a fração inteira nos nós da árvore abaixo do primeiro resultado.

Quando chegarmos ao final de cada caminho, você pode percorrer a árvore para calcular o resultado maximizado de n, somando efetivamente max (n-x) + max (x)

Ie para n = 13, a = 2, b = 3

13 mod 2 = 6 remainder 1
    1 mod 3 = no solution
13 mod 3 = 9 remainder 4
    4 mod 2 = 2 remainder 0

i = 3, j = 2

    
por 27.04.2016 / 20:03
fonte
0

Para recursão, você pode redefinir seu problema inicial  f (n, a, b, c) onde ai + bj + ck = n para  f (n, a, b, c) = ai + f (n-ai, b, c) Onde  f (n, a) torna-se encontrar divisores de n. Eu posso adicionar mais detalhes se você estiver interessado. Atender no celular é um desafio.

    
por 30.04.2016 / 17:28
fonte
0

Para responder à sua pergunta "DP": isso pode ser feito em três etapas:

  1. Encontre as soluções para a*i==m , onde 1<=m<=n : isso é simples, apenas verifique se m%a==0 , então a solução é i = m / a. Se não, então não há solução. Armazene-os em uma matriz.

  2. Encontre as soluções para a*i + b*j==m em que 1<=m<=n , maximizando (i + j): execute o loop em todo j com 1<=j<=m/b , resolva a*i == m-b*j usando os resultados da etapa 1. Para cada m, mantenha o par (i, j) que tem a soma máxima. Se você precisar apenas das somas como resultado, será suficiente manter a soma (i + j) em uma matriz.

  3. Por fim, resolva a*i + b*j + c*k==n fazendo um loop sobre todo o k e usando a etapa 2 para obter a solução para a*i + b*j == n - c*k; maximize(i+j) . Mantenha o triplo (i, j, k) com soma máxima.

por 30.04.2016 / 18:02
fonte