Jump to content
pessantiago

combinações possiveis

Recommended Posts

pessantiago

boas pessoal

tenho uma lista N conjunto de valores, e um unico valor M

N= 1,2,3,4,

M= 5

quero obter todas as combinações possíveis

	public static void main(String[] args) {
   int [] vals ={1,2,3,4} ;
   int sum = 5;

   System.out.println(combinacoes(vals, sum));  
}
  public static int combinacoes( int [] vals,int sum) {
	if (sum < 0) {
		return 0;
	}
	if (vals == null || vals.length == 0) {
		return 0;
	}
  int possiveis[] = new int[sum + 1];
	possiveis[0] = 1;
	for (int i = 0; i < vals.length; ++i) {
		for (int j = vals[i]; j <= sum; ++j) {

			possiveis[j] += possiveis[j - vals[i]];

		}
	}
	return possiveis[sum];

}

queria era retornar

1+4

4+1

2+3

3+2

etc

Edited by Rui Carlos
GeSHi

Share this post


Link to post
Share on other sites
HappyHippyHippo

tens de verificar as seguintes combinações:

X1/X2

X1/X3

...

X1/Xn

X2/X3

X2/X4

...

X2/Xn

X3/X4

X3/X5

...

X3/Xn

...

Xn-1/Xn

e para isso, o teu ciclo interno não faz sentido


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
pessantiago

como assim?

é que nao entendo

quero obter dado um conjuntos de valores N e um numero M inteiro positivo , retornar todas condições possiveis que dêm a suma de 5.

ja andei a procurar no google mas nao chego lá

Share this post


Link to post
Share on other sites
HappyHippyHippo

como assim?

é que nao entendo

explicar mais seria resolver o problema ... olha bem para as combinações que escrevi e pensa em como poderás obter esse "efeito"


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
pessantiago

mas como assim, é que se estive a perceber ja o tinha feito né:P

qual parte do codigo interna?

Share this post


Link to post
Share on other sites
HappyHippyHippo

responde a estas simples questões :

- de onde apareceu o código que apresentaste ?

- o que está a fazer ?

- porque está a fazer o que está a fazer ?


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
HappyHippyHippo

http://stackoverflow.com/questions/4243831/how-to-count-possible-combination-for-coin-problem

título do tópico

How to count possible combination for coin problem

isso é para contar o número de combinações e não para saber quais as combinações !!!

dizer que o resultado do Porto/Zenit ficou no total de 2, não sabes se o Porto marcou 2 e o Zenit nenhum, ou o Zenit marcou dois e o Porto nenhum ou marcaram os dois 1 golo !!!

Apaga esse código e pensa no que escrevi na primeira resposta


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
HappyHippyHippo

conjunto : {X1, X2, X3, ... , XN}

combinações :

X1/X2, X1/X3, X1/X4, ..., X1/Xn-1,   X1/Xn
      X2/X3, X2/x4, ..., X2/Xn-1,   X2/Xn
             X3/X4, ..., X2/Xn-1,   X2/Xn
...
                         Xn-2/Xn-1, Xn-2/Xn
                                    Xn-1/Xn

como disse, mais do que isto é fazer o exercício ...

  • Vote 1

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
pessantiago

entao espera vou ter que ter dois ciclos for né

do tipo

for( int i = 0; i<tamanho.do.array;i++){
  for(int j=i; j<tamanhodoarray; j++)
  }
}

Edited by Rui Carlos
GeSHi

Share this post


Link to post
Share on other sites
Rui Carlos

Sim, é mais ou menos isso.

Uma sugestão: começa por colocar dentro desse ciclo um System.out.println("" + vals + "/" + vals[j]);, e faz as correcções necessárias ao código, até que mostre os pares que o HappyHippyHippo indicou.

Depois de teres todos os pares, só precisarás de um if para seleccionar os pares que cumprem os requisitos.

O passo final será guardar os valores num array (em vez de os imprimir).

Share this post


Link to post
Share on other sites
pessantiago

ja tenho o seguinte codigo

   /**
    * @param args the command line arguments
    */
   public static void main(String[] args) {
      int M = 4;
      int [] array ={1,2,3,4} ;


        System.out.println(findCombinationsCount (M, array));  
   }
  public static int findCombinationsCount(int M, int vals[]) {
       if (M < 0) {
           return 0;
       }
       if (vals == null || vals.length == 0) {
           return 0;
       }

       for (int i = 0; i < vals.length; ++i) {
          for(int j=i+1;j<vals.length;j++)


              System.out.println("" + vals[i] + "/" + vals[j]);

           }

       return 0;

       }

   }


Edited by Rui Carlos
GeSHi

Share this post


Link to post
Share on other sites
pessantiago

a minha duvida agora é isto esta feito de forma exaustiva? testando todas as hipoteses

public class TP8 {
   /**
    * @param args the command line arguments
    */
   public static void main(String[] args) {
       int M = 5;
       int[] array = {1, 2, 3, 4};

       System.out.println(findCombinationsCount(M, array));
   }
   public static int findCombinationsCount(int M, int vals[]) {
       if (M < 0) {
           return 0;
       }
       if (vals == null || vals.length == 0) {
           return 0;
       }
              for (int i = 0; i < vals.length; ++i) {

                   for (int j = i + 1; j < vals.length; j++) {
                       if (M == vals[i] + vals[j]) {
                           System.out.println("" + vals[i] + "/" + vals[j]);
                       }
                   }
               }
     return 0;

   }
}

ajuda me so a retorna o array , é que nao estou a ver como se faz

Share this post


Link to post
Share on other sites
Rui Carlos

Devolver um array não é propriamente óbvio... Precisas mesmo disso, ou o objectivo do exercício é apenas imprimir os valores?

Se for necessário, podes começar por declarar um array para colocares os valores. Tendo em conta que queres devolver pares, penso que será boa ideia um array de bidimensional de tamanho [N*N/2][2], onde N é o tamanho do array de input (N*N/2 é superior ao número de pares que podes encontrar).

Depois, de cada vez que encontrares um elemento, adicionas ao array.

Share this post


Link to post
Share on other sites
pessantiago

o problema é que posso ter N elementos no conjunto por exemplo 1,2,3,4,5,6 dou um inteiro 6 por exemplo,tenho de achar todas os subconjuntos possiveis

1+2+3 =6

1+5 =6

2+4 =6

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.