Jump to content
Localhost

Dynamic programming

Recommended Posts

Localhost

Já ando há alguns dias a estudar e a explorar mais sobre programação dinâmica e acho que ando com problemas sérios.

Eu percebo bem a teoria. Basicamente existem duas maneiras de resolver um problema: top-down (com memoization - guardar resultados para não termos de os re-computar) e bottom-up (guardámos os resultados para partial solutions ou sub-problems e depois vamos construindo soluções para problemas "maiores").

Acho que a teoria está "dominada".

Agora quando tento implementar o que quer que seja tenho tremenda dificuldade. Por exemplo: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=615, neste problema tenho imensas dificuldades em encontrar tanto uma solução com memoization (não sei se existe) como uma solução bottom-up.

Para este problema já construí uma solução recursiva que obviamente não passa no tempo mas agora estou encalhado. Isto aplica-se a todos os problemas - consigo construir a solução recursiva mas depois não consigo passar para DP.

Deixo já agora a solução recursiva para o problema:

#include <cstdio>

using namespace std;

const int coins[] = {1, 5, 10, 25, 50};
long int counter, N;

void dfs (int *set, int j, int i, int sum)
{
if (sum == N)
{
	counter++;

	return;
}

for (int k = 0; k < 5; k++)
{
	if (j > k || coins[k] + sum > N) continue;

	set[i] = coins[k];
	dfs (set, k, i + 1, sum + coins[k]);
}
}

int main ()
{
int set[10000];

scanf ("%ld", &N);
dfs (set, -1, 0, 0);

printf ("Number of ways is %ld\n", counter);

return 0;
}

 


here since 2009

Share this post


Link to post
Share on other sites
Warrior

Falando um pouco do teu código:

- Habitua-te a declarar esse tipo de arrays como o set como global. Normalmente existe um limite de memória diferente para variáveis que ficam na stack (local) e para variáveis que ficam na heap (global) e assim evitamos surpresas desagradáveis. Além disso deixas de ter que passar os apontadores de um lado para o outro.

- De um modo geral não percebo para que queres o set (e por arrasto a variável i) se nunca os utilizas. Podes simplesmente removê-los.

O problema das soluções DP é exactamente esse, conseguir formular a expressão recursiva.

Falando um pouco mais sobre teoria do DP: necessitas de definir um estado e depois encontrar relações entre eles, de modo a conseguires resolver o teu problema para o estado final.

Ligeiro spoiler:

Apesar de existirem várias formas de resolver, o estado mais evidente neste problema é o "número de cêntimos". Muitas vezes a solução para um problema de DP passa por encontrar o estado certo.

Se soubesses a solução para todos os estados "menores" que o estado que pretendes, de que maneira as conseguias usar para calcular a solução do teu problema? (ou seja, sabendo todas as soluções para k < n, como podes obter a solução para n?)

Share this post


Link to post
Share on other sites
Localhost

Em relação ao código, realmente era estúpido ter ali as duas variáveis e já a retirei.

Em relação ao spoiler, o que é que queres dizer com "número de cêntimos"? Eu consegui verificar que quando uma nova moeda (nunca antes utilizada para somas anteriores) um novo número de maneiras para a soma actual é calculado. Só não consigo encontrar a relação...


here since 2009

Share this post


Link to post
Share on other sites
Warrior

A pergunta que te é colocada é: quantas formas diferentes existem de formar N cêntimos.

Se soubesses a resposta para todos os valores k < N, consegues usá-los para descobrir a resposta para N?

Usando o exemplo do segundo input: tu queres saber quantas formas existem de somar 26; se souberes a resposta para 1, 2, 3, ..., 24 e 25 consegues descobrir a resposta para 26?

Share this post


Link to post
Share on other sites
Localhost

Provavelmente sim. Se conseguíssemos saber a quantidade de combinações de moedas novas que existia para 26 relativamente a 25, não?


here since 2009

Share this post


Link to post
Share on other sites
Warrior

Problemas de DP andam muito em torno disso, construir soluções complicadas a partir de soluções mais simples.

Repara que se conseguires descobrir qual é a regra que relaciona sol(n) com os valores de sol(k), k <n, então consegues resolver o problema.

Porque evidentemente que sol(0) = 0 (caso base) e depois aplicando a regra descobres todos os outros.

A diferença entre DP e memoization está na forma como calculas sol(). DP calculas tipicamente com um ciclo começando nos mais simples, memoization colocas a fórmula explicitamente numa função recursiva que te calcula os valores necessários ou aproveita os anteriormente calculados.

Share this post


Link to post
Share on other sites
Localhost

O problema encontra-se precisamente em descobrir a tal regra, a tal relação entre sol(n) e sol(k), k < n. Eu já tinha noção que se descobríssemos sol(k) poderíamos descobrir sol(k + 1) e assim sucessivamente. O problema encontra-se precisamente em encontrar essa relação.

Como posso treinar este processo de encontrar as relações? Achas que este problema que apresentei é muito complicado para eu começar? Por onde começo?


here since 2009

Share this post


Link to post
Share on other sites
Localhost

Desisti, temporariamente, deste problema e segui para outro para ver se conseguia alguma coisa (nem que seja para ganhar ânimo lol) e encontrei este: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=1406.

Resumindo, além deste aqui me parecer mais intuitivo e de eu achar que já consegui encontrar o estado necessário (que é o tempo disponível que ele tem) não consigo encontrar a relação entre os estados.

Exemplo de input:

3 5 10

Output:

2

Eu sei que começávamos com o caso base com t = 0 (a solução era 0 - não podemos comer nenhum hambúrguer se temos 0 minutos) e depois a partir daí fazíamos um bottom-up. Mas como é que relacionávamos? Aí está a minha dúvida...


here since 2009

Share this post


Link to post
Share on other sites
xtrm0

Acho que nao percebi bem o enunciado,

Mas o que aquilo diz, não é para, simplesmente, calcular o maximo de hamburguers, que demoram menos tempo a comer, menores que t:

int h=t/min(n,m);
t = t-(t%min(n,m));
while (t-max(n,m)>=0) {
t=t-max(n,m);
h++;
}
cout << h << endl:
if (t>0) cout << t << endl;


<Signature goes here>

Share this post


Link to post
Share on other sites
Localhost

Podes explicar o que código que apresentaste? Não testei...


here since 2009

Share this post


Link to post
Share on other sites
Warrior

Estes dois problemas são muito semelhantes, portanto acho que quando descobrires a solução para um descobres para o outro. No entanto acho o primeiro ligeiramente mais fácil, talvez porque o enunciado me parecer mais intuitivo.

Não conheço nenhuma forma de aprender DP sem ser treinando e batendo com a cabeça na parede..

Talvez devesses começar pelo "outro" problema típico de moedas, o problema do troco, que eu considero ainda mais intuitivo do que este:

Dados N tipos diferentes de moedas, e um valor a fornecer de troco m, qual o número mínimo de moedas a utilizar?

Por exemplo com moedas de {1, 3, 5, 8, 10} e para atingir o valor 13, o número mínimo de moedas é 2, 5+8.

xtrm0: repara que ele quer comer o maior número de hambúrgueres sem desperdiçar tempo, ou seja, tentando colocar o tempo restante a 0. Mas admito que não percebi bem o que fizeste e que até pode funcionar; este caso particular com 2 tipos de hambúrgueres parece-me ter soluções sem ser DP.

Share this post


Link to post
Share on other sites
xtrm0

Esquece. Acabei de perceber que o código que fiz está mal.


<Signature goes here>

Share this post


Link to post
Share on other sites
Localhost

Warrior: esse problema já o tinha resolvido e já o tinha percebido. Depois de ver a solução (que estava no tutorial de dp no topcoder) é relativamente fácil de ver a relação entre os estados. Vou tentar resolver mais problemas de dp e tentar arranjar as tais relações.

Já agora, não me consegues arranjar aí nenhum problema mesmo simples para eu começar por algum lado?


here since 2009

Share this post


Link to post
Share on other sites
Localhost

Sei decorando o processo, no entanto, a mim parece-me black magic lol.


here since 2009

Share this post


Link to post
Share on other sites
mogers

Sei decorando o processo, no entanto, a mim parece-me black magic lol.

Enquanto não for intuitivo para ti, é como não saber. O knapsack parece-me o problema mais simples, devias investir nesse. Não há magia aqui, só mesmo

Não conheço nenhuma forma de aprender DP sem ser treinando e batendo com a cabeça na parede..


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Localhost

Vou tentar então começar com o knapsack. Depois qualquer dúvida sobre isto posto aqui. Obrigado.


here since 2009

Share this post


Link to post
Share on other sites
Localhost

Tive mais tempo e já consegui perceber bem o knapsack. Ainda me falta entender melhor um bocadinho a implementação bottom-up em vez da memoization.

Depois de ter compreendido melhor o knapsack tentei resolver o problema homer simpson do UVa.

Deixo aqui o link e o código: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=1406.

#include <cstdio>
#include <climits>
#include <algorithm>

using namespace std;

int m, n, t;
unsigned int drink[100000], steps[100000];

void input ()
{
for (int k = 0; k < 100000; k++)
	drink[k] = steps[k] = -1;

scanf ("%d %d %d", &m, &n, &t);

return;
}

int hs_2 (int sum, int *beer)
{
int beer_left = 0, beer_right = 0, steps_left = 0, steps_right = 0;

if (steps[sum] != -1)
{
	*beer = drink[sum];
	return steps[sum];
}

if (sum == 0) return 0;

if (sum - m >= 0) steps_left = 1 + hs_2 (sum - m, &beer_left);
else beer_left = sum;

if (sum - n >= 0) steps_right = 1 + hs_2 (sum - n, &beer_right);
else beer_right = sum;

if (beer_right > beer_left)
{
	*beer = beer_left;
	drink[sum] = beer_left;

	return steps_left;
}

*beer = beer_right;
drink[sum] = beer_right;

steps[sum] = beer_right < beer_left ? steps_right: max (steps_right, steps_left);

return beer_right < beer_left ? steps_right: max (steps_right, steps_left);
}

int main ()
{
int beer = 0;

input ();

printf ("%d", hs_2 (t, &beer));
if (beer > 0)
	printf (" %d", beer);

putchar ('\n');

return 0;
}

Além de todos os casos que meto no meu programa darem correctos (já andei pelo fórum do UVa a ver os casos críticos e mesmo esses deram correctamente) está-me a dar WA. Alguém tem uma ideia sobre isto? Será que tem alguma coisa a ver com o output, com o seu formato...?

O código em si utiliza memoization; calcula o resultado óptimo para um determinado tempo, guarda e depois utiliza mais tarde. Tive que utilizar alguns truques esquisitos para a parte de calcular a menor quantidade de cerveja (ponteiros) mas no final deu tudo certo...


here since 2009

Share this post


Link to post
Share on other sites
pedrosorio

"Input consists of several test cases. Each test case consists of three integers m, n, t (0 < m,n,t < 10000). Input is terminated by EOF."


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
Baderous

O return; no fim de uma função cujo tipo de retorno é void é dispensável.

Share this post


Link to post
Share on other sites
Localhost

pedrosorio: bah.. isso é tão típico meu.

Baderous: thanks.

Finalmente tive accepted em 2,208s. Alguém tem alguma dica para dar sobre o código e o algoritmo em si? Hoje vou tentar perceber a solução bottom-up para logo tentar implementar. Já consegui perceber que tendo a solução óptima para um tempo mais pequeno (t' < t) podemos depois construir a solução para tempos maiores através da recursion tree que fiz para a memoization. Agora só me falta perceber como vou implementar e dar uns últimos ajustes...

A solução bottom-up é mais rápida que a memoization? É que pelo pensei a memoization corta logo um bom bocado da árvore e só calcula o que precisa enquanto que a bottom-up vai ter que fazer computações um bocado desnecessárias...

Já agora deixo aqui o código final:

#include <cstdio>
#include <climits>
#include <algorithm>

using namespace std;

int m, n, t;
unsigned int drink[100000], steps[100000];

int hs_2 (int sum, int *beer)
{
int beer_left = 0, beer_right = 0, steps_left = 0, steps_right = 0;

        // uso da memoization, vai aos vectores e retira os valores óptimos se já os tiver calculado
if (steps[sum] != -1)
{
	*beer = drink[sum];
	return steps[sum];
}

if (sum == 0) return 0;

if (sum - m >= 0) steps_left = 1 + hs_2 (sum - m, &beer_left);
else beer_left = sum;

if (sum - n >= 0) steps_right = 1 + hs_2 (sum - n, &beer_right);
else beer_right = sum;

if (beer_right > beer_left)
{
	*beer = beer_left;

	steps[sum] = steps_left; // guarda valores óptimos
	drink[sum] = beer_left;

	return steps_left;
}

*beer = beer_right;
drink[sum] = beer_right;

steps[sum] = beer_right < beer_left ? steps_right: max (steps_right, steps_left);

return beer_right < beer_left ? steps_right: max (steps_right, steps_left);
}

int main ()
{
int beer = 0;

while (scanf ("%d %d %d", &m, &n, &t) != EOF)
{
	for (int k = 0; k < 100000; k++)
		drink[k] = steps[k] = -1;

	printf ("%d", hs_2 (t, &beer));
	if (beer > 0)
		printf (" %d", beer);

	putchar ('\n');
}

return 0;
}


here since 2009

Share this post


Link to post
Share on other sites
Warrior

É um pau de dois bicos..

Por um lado, memoization só calcula os valores estritamente necessários.

Por outro lado, os valores estritamente necessários frequentemente são todos. Além disso, implementações recursivas são normalmente mais lentas do que iterativas e muitas vezes, apesar de fazeres lookup, estás a chamar a função várias vezes com o mesmo valor..

Share this post


Link to post
Share on other sites
pedrosorio

A solução bottom-up é mais rápida que a memoization?

OFF-TOPIC: Este problema não precisa de dp, portanto neste caso é bastante mais rápido fazer um ciclo for (0.064s).


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
Localhost

Cheguei a algumas conclusões importantes sobre a bottom-up.

Neste caso, podíamos analisar cada nó (cada tempo disponível de 0 até t) e verificar que temos duas alternativas.. comer um hambúrguer que demora m minutos ou um que demora n minutos.

Vou dar um exemplo para explicar o que pensei para se tornar mais fácil.

Supondo que: m = 2, n = 3, t = 10.

Sabemos imediatamente que para t = 0 a quantidade máxima de hambúrgueres vai ser 0 e a cerveja que bebe também. Este é o caso base.

Vamos para t = 1. Aqui temos duas opções (t - 2 e t - 3). Ambas são menores que 0 logo podemos concluir que ele para t = 1 pode comer um máximo de 0 hambúrgueres (visto que nenhuma opção vai ser >= 0) e beber t tempo cerveja (1). Então: beer[1]  = t e hamb[1] = 0;

Vamos para t = 2. Duas opções outra vez (2 - 2 = 0 e 2 - 3 = -1). Como a primeira opção é igual a 0 vamos a beer[0] e a hamb[0] e retirámos os seus valores. Então: beer[2] = beer[t - m] (0) e hamb[2] = 1 + hamb[t - m]. A segunda opção é < 0 logo: if (beer[t] > t) beer[t] = t e hamb[t] = 1 (penso que esta condição nunca vai ser verdadeira...?).

Para t = 3 o caso já se torna mais interessante. Duas opções (3 - 2 = 1 e 3 - 3 = 0). Vamos avaliar as duas. Para o primeiro caso fazemos: beer[t] = beer[t - m] e hamb[t] = 1 + hamb[t - m]. Para o segundo if (beer[t] > beer[t - n]) beer[t] = beer[t - n] e hamb[t] = 1 + hamb[t - n].

Repetíamos o processo até o final, em hamb[t] e beer[t] estaria a nossa resposta. Neste caso então só precisávamos de um ciclo. Isto está correcto...?


here since 2009

Share this post


Link to post
Share on other sites
Localhost

Já implementei a ideia de bottom-up mas está-me a dar mal em alguns casos.. tenho que analisar bem.

Se alguém quiser comentar o código que tenho até agora está à vontade.

#include <cstdio>
#include <climits>
#include <algorithm>

using namespace std;

const int MAX = 10010;

int hamb[MAX], beer[MAX], m, n, t;

void init_arrays ()
{
for (int k = 0; k < MAX; k++) hamb[k] = beer[k] = INT_MAX;

hamb[0] = beer[0] = 0;
}

int main ()
{
while (scanf ("%d %d %d", &m, &n, &t) != EOF)
{
	init_arrays ();

	for (int i = 1; i <= t; i++)
	{
		if (i - m < 0)
		{
			hamb[i] = 0;
			beer[i] = i;
		}
		else
		{
			if (beer[i] > beer[i - m])
			{
				hamb[i] = 1 + hamb[i - m];
				beer[i] = beer[i - m];
			}
			else if (beer[i] == beer[i - m])
				hamb[i] = 1 + max (hamb[i], hamb[i - m]);
		}

		if (i - n < 0)
		{
			if (i < beer[i])
				beer[i] = i;
		}
		else
		{
			if (beer[i] > beer[i - n])
			{
				hamb[i] = 1 + hamb[i - n];
				beer[i] = beer[i - n];
			}
			else if (beer[i] == beer[i - n])
				hamb[i] = 1 + max (hamb[i], hamb[i - n]);
		}
	}

	printf ("%d", hamb[t]);
	if (beer[t] > 0)
		printf (" %d", beer[t]);

	putchar ('\n');
}

return 0;
}


here since 2009

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.