Estou tentando gerar todas as combinações possíveis de somas entre elementos de uma lista que resultem em um n estabelecido. Eu tentei os código abaixo mas não estou conseguindo limitar apenas aos itens da lista.
public static void main(String[] args) {
int n = 10;
int [ ] valores = {2,3,4};
for(int a = valores[0]; a <= n; a++) {
for(int b = valores[1]; b <= n; b++) {
for(int c = valores[2]; c <= n; c++) {
int soma = a+b+c;
if(soma==n)
System.out.printf("%d + %d + %d = %d \n",a,b,c, soma);
}
…
int n = 10;
List<Integer> lista = Arrays.asList(2,3,4,5);
for(int a = lista.get(0); a <= lista.get(3); a++) {
for(int b = lista.get(1); b <= lista.get(3); b++) {
for(int c = lista.get(2); c <= lista.get(3); c++) {
int soma = a+b+c;
if(soma==n)
System.out.printf("%d + %d + %d = %d \n",a,b,c, soma);
}
}
Opa, o objetivo é pegar os valores que estão na lista e fazer uma soma com esses valores que resultem no valor do n “n = 10 nesse caso”.
ex: [ 2, 3, 4 ]
2 + 4 + 4 = 10
3 + 3 + 4 = 10
No primeiro algoritmo que eu fiz se eu acrescentar o numero 6 na lista [2, 3, 4, 6] ele retorna combinações com o numero 5 também que no caso não estaria na lista, o objetivo é que as combinações de soma sejam feita apenas com os numeros que estiverem na lista.
int[] v = { 2, 4, 5, 6, 9, 10 };
for ( int i = 0; i < v.length; i++ ) {
for ( int j = i + 1; j < v.length; j++ ) {
for ( int k = j + 1; k < v.length; k++ ) {
if ( v[i] + v[j] + v[k] == n ) {
// a soma da trinca é igual a n
}
}
}
}
Se vc pensar em n = 0, vc tem o problema chamado ThreeSum (3SUM). A solução trivial acima é lenta para quantidades grandes de elementos que precisam ser combinados, pois o algoritmo tem crescimento cúbico. A melhoria para a ordem quadrática envolve usar busca binária para encontrar o inverso da soma de v[i] e v[j], ajustada para n caso n seja diferente de zero. Vc pode dar uma olhada aqui se quiser saber mais sobre: 3SUM - Wikipedia
tentei esse algoritmo também mas ao excluir o 5 da lista e incluir o 3, ele continua utilizando o 5 na combinação das somas.
int n = 10;
int[] v = { 2, 3, 4, 6, 9, 10 };
for ( int i = 0; i < v.length; i++ ) {
for ( int j = i + 1; j < v.length; j++ ) {
for ( int k = j + 1; k < v.length; k++ ) {
if ( v[i] + v[j] + v[k] == n ) {
}
int soma = i+j+k;
if(soma==n)
System.out.printf("%d + %d + %d = %d \n",i,j,k, soma);
}
}
}
Primeiro você está ignorando completamente o if que verifica se a soma dos valores é 10.
Segundo, você está somando os índices e não os valores do array.
O correto é assim, como o @davidbuzatto ensinou, mas você ignorou o código dele
int n = 10;
int[] v = {2, 3, 4, 6, 9, 10};
for (int i = 0; i < v.length; i++) {
for (int j = i + 1; j < v.length; j++) {
for (int k = j + 1; k < v.length; k++) {
int soma = v[i] + v[j] + v[k];
if (soma == n) {
System.out.printf("%d + %d + %d = %d %n", v[i], v[j], v[k], soma);
}
}
}
}
Estou iniciando agora, imaginei que tinha algo errado na hora de chamar o printf, até tentei resolver sozinho mas não sabia que dava pra chamar v[ i ]…
Mas brigadão pela ajuda dos colegas, tem me ajudado muito aqui…aos poucos vou pegando o jeito.
Tentei rodar o algoritmo aqui como você sugeriu mas ele não ta imprimindo nada no console…
Nobres eu to tentando solucionar um desafio porém queria tentar ver até onde chego sozinho, mas creio que falta informação na forma como eu expus o problema, então vou passar exatamente como eu recebi o desafio talvez esclareça melhor o que precisa ser executado.
Dado um vetor de números e um número n. Determine a soma com o menor número de elementos entre os números do vetor mais próxima de n e também mostre os elementos que compõem a soma. Para criar a soma, utilize qualquer elemento do vetor uma ou mais vezes.
Exemplo:
Entrada de dados:
N = 10
V = [2, 3, 4]
Saída de dados:
10
[2, 4, 4]
[3, 3, 4]
Explicação:
Se N = 10 e V = [2, 3, 4] você pode utilizar as seguintes soma: [2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 4, 4] ou [3, 3, 4]. Como a quantidade de elementos em [2, 4, 4] e [3, 3, 4] é igual, os dois conjuntos devem ser mostrados.
O pulo do gato é usar programação dinâmica para computar todas as formas possíveis e então, para o seu caso, coletar as que tem a menor quantidade de moedas.
O problema do troco da uma luz, mas ele retorna a quantidade de possibilidades de somas, neste caso eu preciso que imprima as somas em si com o menor numero de elementos da lista.
Se você parar e com calma dar uma olhada no que o código faz, você vai conseguir identificar onde é feita essa contagem e, adivinhe só, é ali que vc vai coletar os possíveis trocos e depois escolher os que têm menos moedas. Vc mesmo disse que quer entender, então mãos na massa.
