Mother's Milk

[polska]

Boas pessoal, estou a resolver o problema da USACO Mother's Milk, e pensei numa DFS, penso que seja um problema que enquadre muito bem nesta resolução, então implementei o programa, e uma função void dfs, o problema, é que não estou a perceber que condições devo colocar... o problema é o seguinte:

Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.

Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

PROGRAM NAME: milk3

INPUT FORMAT

A single line with the three integers A, B, and C.

SAMPLE INPUT (file milk3.in)

8 9 10

OUTPUT FORMAT

A single line with a sorted list of all the possible amounts of milk that can be in bucket C when bucket A is empty.

SAMPLE OUTPUT (file milk3.out)

1 2 8 9 10

Eu percebo o que pede pede o problema, devo imprimir todos os valores que o balde C por conter quando o balde A esta vazio.. Porém, não estou a entender que condições devo colocar na minha função dfs, eu já coloquei o mapa dos baldes que já verifiquei e um array com os valores possiveis, mas as condições não estou a consseguir..

este e o meu code, quem me puder ajudar:

#include <stdio.h>
#include <assert.h>

bool verificado[21][21][21], can[21]; //inteiros entre 1 e 20, inclusive
int a, b, c;

/* DFS - Depth first search */
void dfs( int bA, int bB, int bC )
{
//verifica se a possibilidade (bA,bB) ja foi testada, se foi não repete o teste
if( verificado[bA][bB][bC] )
 return;

//marca a possibilidade (bA,bB,bC) como testada, para a próxima vez não passar na condição acima
verificado[bA][bB][bC] = true;

//se bA esta vazia então bC é um dos resultados
if( bA == 0 )
 can[bC] = true;

//condicoes...



}

int main()
{
FILE *in, *out;
in = fopen( "milk3.in", "r" );
out = fopen( "milk3.out", "w" );
assert( in != NULL && out != NULL );

//recebe a, b, c
fscanf( in, "%d %d %d", &a, &b, &c );

dfs( 0, 0, c );

for( int i=0; i<c; i++ )
{
 if( can[i] )
  printf( "%d ", i );
}
printf( "\n" );

return 0;
}

[pmg]

Repara que numa determinada situação (por exemplo: 2 litros no balde A, 3 no B e 5 no C) só podes evoluir para seis situações (não obrigatoriamente distintas): podes passar do balde A para o balde B ou C (0-5-5 ou 0-3-7), do balde B para A ou C (5-0-5 ou 2-0-8), e do balde C para o balde A ou B (7-3-0 ou 2-8-0). Cada passagem é completa, isto é, ou enches o balde destino ou esvazias o balde origem.

/* calcular tAB, tAC, tBA, tBC, tCA, tCB: as transferencias de um balde para outro */
dfs(bA-tAB, bB+tAB, bC); /* Balde A para B */
dfs(bA-tAC, bB, bC+tAC); /* Balde A para C */
dfs(bA+tBA, bB-tBA, bC); /* Balde B para A */
dfs(bA, bB-tBC, bC+tBC); /* Balde B para C */
dfs(bA+tCA, bB, bC-tCA); /* Balde C para A */
dfs(bA, bB+tCB, bC-tCB); /* Balde C para B */

Edited July 11, 2012 at 11:53 AM by pmg

[Warrior]

Faltam aí uns mínimos/máximos para garantir que não se ultrapassam as capacidades dos baldes.

[polska]

Repara que numa determinada situação (por exemplo: 2 litros no balde A, 3 no B e 5 no C) só podes evoluir para seis situações (não obrigatoriamente distintas): podes passar do balde A para o balde B ou C (0-5-5 ou 0-3-7), do balde B para A ou C (5-0-5 ou 2-0-8), e do balde C para o balde A ou B (7-3-0 ou 2-8-0). Cada passagem é completa, isto é, ou enches o balde destino ou esvazias o balde origem.

/* calcular tAB, tAC, tBA, tBC, tCA, tCB: as transferencias de um balde para outro */
dfs(bA-tAB, bB+tAB, bC); /* Balde A para B */
dfs(bA-tAC, bB, bC+tAC); /* Balde A para C */
dfs(bA+tBA, bB-tBA, bC); /* Balde B para A */
dfs(bA, bB-tBC, bC+tBC); /* Balde B para C */
dfs(bA+tCA, bB, bC-tCA); /* Balde C para A */
dfs(bA, bB+tCB, bC-tCB); /* Balde C para B */

hum, assim já começo a pensar nas condições 🙂

Thanks

Faltam aí uns mínimos/máximos para garantir que não se ultrapassam as capacidades dos baldes.

Como assim? Passar o mínimo de algo e o máximo de algo para a função?

[pmg]

hum, assim já começo a pensar nas condições 🙂

Nao te preocupes com as condicoes ... vais ver que chega aquela que ja escreveste (if (verificado...) return;)

[polska]

Nao te preocupes com as condicoes ... vais ver que chega aquela que ja escreveste (if (verificado...) return;)

sim, mas estou a falar daquelas que tenho que fazer para usar :

dfs(bA-tAB, bB+tAB, bC); /* Balde A para B */

dfs(bA-tAC, bB, bC+tAC); /* Balde A para C */

dfs(bA+tBA, bB-tBA, bC); /* Balde B para A */

dfs(bA, bB-tBC, bC+tBC); /* Balde B para C */

dfs(bA+tCA, bB, bC-tCA); /* Balde C para A */

dfs(bA, bB+tCB, bC-tCB); /* Balde C para B */

[pmg]

Por exemplo, a transferencia de A para B é uma de duas hipoteses:

1) ou é tudo o que esta no A

2) ou é o suficiente para encher B

destas duas tens de escolher a mais pequena, mesmo que seja zero

nao precisas de mais condicoes.

[polska]

Por exemplo, a transferencia de A para B é uma de duas hipoteses:

1) ou é tudo o que esta no A

2) ou é o suficiente para encher B

destas duas tens de escolher a mais pequena, mesmo que seja zero

nao precisas de mais condicoes.

então vou ter 6 condições, duas para cada balde.

por exemplo para o A verifico se esta vazio ou nao e se da para encher o B ou C , para o B e C a mesma coisa, certo?

Edited July 11, 2012 at 08:45 PM by polska

[pmg]

Podes fazer assim, como dizes ... mas repara:

se o balde A esta vazio, quando passas 0 litros para o balde B e chamas a funcao recursivamente (com os mesmos valores), a primeira coisa que a funcao faz 'e verificar que o DFS ja passou por essa combinacao e retorna imediatamente.

Como dizes, podes fazer uma condicao e nao chamar a funcao recursivamente ... mas, isso, acho eu, so vai complicar o codigo sem ganhar nada significativo em performance

/* versao com condicoes */
if (bA) {
   tAB = min(bA, <MAXB> - bB); /* min devolve o valor mais pequeno; <MAXB> tem a capacidade do balde B */
   dfs(bA - tAB, bB + tAB, bC);
   tAC = min(bA, <MAXC> - bC); /* tAC nao pode ser zero */
   dfs(bA - tAC, bB, bC + tAC);
}
if (bB) {
   /* ... */
}
/* ... */

/* versao sem condicoes (alem da primeira condicao "recursiva") */
tAB = min(bA, <MAXB> - bB); /* min e o que espera; <MAXB> e a capacidade do balde B */
dfs(bA - tAB, bB + tAB, bC);
tAC = min(bA, <MAXC> - bC); /* pode ser zero */
dfs(bA - tAC, bB, bC + tAC);
/* ... */

[polska]

Podes fazer assim, como dizes ... mas repara:

se o balde A esta vazio, quando passas 0 litros para o balde B e chamas a funcao recursivamente (com os mesmos valores), a primeira coisa que a funcao faz 'e verificar que o DFS ja passou por essa combinacao e retorna imediatamente.

Como dizes, podes fazer uma condicao e nao chamar a funcao recursivamente ... mas, isso, acho eu, so vai complicar o codigo sem ganhar nada significativo em performance

/* versao com condicoes */
if (bA) {
tAB = min(bA, <MAXB> - bB); /* min devolve o valor mais pequeno; <MAXB> tem a capacidade do balde B */
dfs(bA - tAB, bB + tAB, bC);
tAC = min(bA, <MAXC> - bC); /* tAC nao pode ser zero */
dfs(bA - tAC, bB, bC + tAC);
}
if (bB) {
/* ... */
}
/* ... */

/* versao sem condicoes (alem da primeira condicao "recursiva") */
tAB = min(bA, <MAXB> - bB); /* min e o que espera; <MAXB> e a capacidade do balde B */
dfs(bA - tAB, bB + tAB, bC);
tAC = min(bA, <MAXC> - bC); /* pode ser zero */
dfs(bA - tAC, bB, bC + tAC);
/* ... */

Ouve aqui uma confusão pmg 😄 , fiz-me entender mal, eu tou a pensar em fazer recursivamente claro, não faz muito sentido que seja de outra mamenira, mas repara, eu não vou simplesmente chegar ao meu codigo e colar isto:

dfs(bA-tAB, bB+tAB, bC); /* Balde A para B */

dfs(bA-tAC, bB, bC+tAC); /* Balde A para C */

dfs(bA+tBA, bB-tBA, bC); /* Balde B para A */

dfs(bA, bB-tBC, bC+tBC); /* Balde B para C */

dfs(bA+tCA, bB, bC-tCA); /* Balde C para A */

dfs(bA, bB+tCB, bC-tCB); /* Balde C para B */

Tenho de ter uma condição para saber cada chamada recursiva, se isto e isto acontece chamo a função com seguintes parâmetros, se acontecer isto e isto já chamo com outros parâmetros..

Edited July 11, 2012 at 09:11 PM by polska

[pmg]

... mas repara, eu não vou simplesmente chegar ao meu codigo e colar isto:

dfs(bA-tAB, bB+tAB, bC); /* Balde A para B */
dfs(bA-tAC, bB, bC+tAC); /* Balde A para C */
dfs(bA+tBA, bB-tBA, bC); /* Balde B para A */
dfs(bA, bB-tBC, bC+tBC); /* Balde B para C */
dfs(bA+tCA, bB, bC-tCA); /* Balde C para A */
dfs(bA, bB+tCB, bC-tCB); /* Balde C para B */

Porque? 🙂

Se os tAB, tAC, tBA, tBC, tCA, e tCB forem bem calculados (como exemplificado no meu post anterior) vai funconar 😛

[polska]

Conssegui, obrigado pmg 🙂

/* A para B && A para C */
tAB = min(bA, b - bB);
dfs(bA - tAB, bB + tAB, bC);
tAC = min(bA, c - bC);
dfs(bA - tAC, bB, bC + tAC);
/* B para A && B para C */
tBA = min(bB, a - bA);
dfs(bA + tBA, bB - tBA, bC);
tBC = min(bB, c - bC);
dfs(bA, bB-tBC, bC + tBC);
/* C para A && C para B */
tCA = min(bC, a-bA);
dfs(bA + tCA, bB, bC - tCA);
tCB = min(bC, b-bB);
dfs(bA, bB + tCB, bC - tCB);

Edited July 12, 2012 at 09:35 PM by polska

[polska]

Já agora, eu implementei uma dfs, ela percorre todos os caminhos e volta atrás quando um já foi verificado. Agora, se eu quisesse implementar uma bfs, como tinha que fazer, é que esta-me a fazer confusão, eu sei que numa bfs primeiro verifica todos os caminhos possíveis de um nó, e depois quando já foram todos verificados, passa para outro, e volta a verificar todos os possiveis..

Mas como implementar? Eu não sei se neste problema era possível, mas só mesmo para servir de exemplo..

[pmg]

A BFS vai pesquisando aos bocadinhos: primeiro todos os bocadinhos de comprimento 1, depois os bocadinhos de comprimento 2, depois os de 3, ...

Normalmente implementa-se com recurso a uma estrutura FIFO (uma queue). Basicamente:

1) mete o primeiro nó na queue

2) se a queue estiver vazia: terminar

3) retira um elemento da queue (o primeiro), marca-o visitado

4) mete todos os "filhos" não visitados desse elemento na queue

5) ir para 2

Edited July 13, 2012 at 02:07 PM by pmg

[polska]

A BFS vai pesquisando aos bocadinhos: primeiro todos os bocadinhos de comprimento 1, depois os bocadinhos de comprimento 2, depois os de 3, ...

Normalmente implementa-se com recurso a uma estrutura FIFO (uma queue). Basicamente:

1) mete o primeiro nó na queue

2) se a queue estiver vazia: terminar

3) retira um elemento da queue (o primeiro), marca-o visitado

4) mete todos os "filhos" não visitados desse elemento na queue

5) ir para 2

O primeiro nó então seria o, 0 0 c , e guardava na queue . Mas depois como é que eu sabia que ja tinha todos os bocados deste nó?

Já agora, as chamadas da função mantinham-se certo?

[pmg]

Exemplo para capacidades 8 9 10

queue: (0 0 10)

removes o (0 0 10) e marcas visitado;

queue: --

metes na queue os "filhos nao visitados de (0 0 10)": (0 0 10) (0 0 10) (0 0 10) (0 0 10) (8 0 2) (0 9 1)

queue: (8 0 2) (0 9 1)

removes o (8 0 2) e marcas visitado;

queue: (0 9 1)

metes na queue os "filhos nao visitados de (8 0 2)": (0 8 2) (0 0 10) (8 0 2) (8 0 2) (8 0 2) e (8 2 0)

queue: (0 9 1) (0 8 2) (8 2 0)

removes o (0 9 1) e marcas visitado;

queue: (0 8 2) (8 2 0)

metes na queue os "filhos nao visitados de (0 9 1)": (0 9 1) (0 9 1) (8 1 1) (0 0 10) (1 9 0) (0 9 1)

queue: (0 8 2) (8 2 0) (8 1 1) (1 9 0)

...

Edited July 13, 2012 at 06:01 PM by pmg

[polska]

eu estou a fazer a class da queue, mas não sei de que tipo deve ser a queue, um array? uma matriz?? Falta-me isso para completar as funções push e pop

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 21

class queu
{
private:
bool visisted[MAX][MAX][MAX];
bool can[MAX];
int queue[MAX][3]; // ?
int add;
int del;

public:
queu()
{
 add = -1;
 del = -1;
}

void push()
{
 if( add == -1 )
  add = del = 0;
 else
 {
  add++;
  if( add == MAX )
  {
   add--;
   return;
  }
 }
}

void pop()
{
 int tmp;
 if( del != -1 )
 {
  for( int i=0; i<=add; i++ )
  {
   if( (i+1) <= add )
   {

   }
  }
 }
}
};

int main()
{
   return 0;
}

[mogers]

Uma fila de pessoas é basicamente uma linha. Um array pode ser visto como uma linha de uma matriz, logo uma matriz não é adequada para implementar uma fila. Um array é uma das hipoteses, outra seria uma lista ligada.

Neste tipo de pesquisa tens de definir qual é o teu estado da pesquisa. Neste caso, o estado é a quantidade em cada um dos 3 baldes. A fila contém uma sequência de estados, por isso a classe fila não terá coisas como visisted[MAX][MAX][MAX] mas sim algo como

struct Estado {
  int a,b,c;
};
struct Queue {
  Estado fila[MAX];
  int inicio, fim;
// ...
};

PS: porque é que na última versão do forum, ao copiar um bocado de código de um post é copiada a formatação também? :/

[pmg]

#include <iostream>
#include <algorithm>

Ah! Estás a usar uma linguagem que já tem uma implementação duma queue na biblioteca standard.

A minha sugestão é que uses as facilidades da linguagem que escolheste, em vez de estares a reinventar a roda.

Não usares a queue da Standard Library é o mesmo que teres um carro mas andares a pé porque não queres usar a chave.

[Warrior]

Ah! Estás a usar uma linguagem que já tem uma implementação duma queue na biblioteca standard.

A minha sugestão é que uses as facilidades da linguagem que escolheste, em vez de estares a reinventar a roda.

Não usares a queue da Standard Library é o mesmo que teres um carro mas andares a pé porque não queres usar a chave.

Não concordo totalmente. Andar a pé faz muito bem.

Implementa uma queue pelo menos uma vez; a partir daí usa o que a tua linguagem te oferece.