-6

Eu tenho esses valores:

x = 5;

long[] b = new long[]{5,1,2,3};

Preciso fazer um programa que some os itens do array b de forma que o resultado seja sempre igual a 5(x). Pode repetir os itens, tipo: [1,1,1,1,1] ou [5] ou [2,3] ou [1,1,3] ou [1,1,1,2] ou [2,2,1] dessa forma a saída seria 6, a resposta deverá ser a qde de possibilidades. A minha dúvida seria como fazer esse somatório de forma separada.

EDIT1

Esse é o problema original

You are working at the cash counter at a fun-fair, and you have different types of coins available to you in infinite quantities. The value of each coin is already given. Can you determine the number of ways of making change for a particular number of units using the given types of coins?

For example, if you have types of coins, and the value of each type is given as respectively, you can make change for units in three ways: , , and .

Complete the function getWays that takes the number of coin types and the value of each coin type as input, and return the number of ways to make change for units using any number of coins.

Input Format

The first line contains two space-separated integers describing the respective values of and , where: is the number of units is the number of coin types The second line contains space-separated integers describing the respective values of each coin type : (the list of distinct coins available in infinite amounts).

Constraints

Each is guaranteed to be distinct. Hints

Solve overlapping subproblems using Dynamic Programming (DP): You can solve this problem recursively but will not pass all the test cases without optimizing to eliminate the overlapping subproblems. Think of a way to store and reference previously computed solutions to avoid solving the same subproblem multiple times. * Consider the degenerate cases: - How many ways can you make change for cents? - How many ways can you make change for cents if you have no coins? * If you're having trouble defining your solutions store, then think about it in terms of the base case . - The answer may be larger than a -bit integer.

Output Format

Print a long integer denoting the number of ways we can get a sum of from the given infinite supply of types of coins.

Sample Input 0

4 3

1 2 3

Sample Output 0

4

Explanation 0

There are four ways to make change for using coins with values given by :

Thus, we print as our answer.

Sample Input 1

10 4

2 5 3 6

Sample Output 1

5

Explanation 1

There are five ways to make change for units using coins with values given by :

Thus, we print as our answer.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
    static long getWays(long n, long[] c){
        // Complete this function
    }

    static void Main(String[] args) {
        string[] tokens_n = Console.ReadLine().Split(' ');
        int n = Convert.ToInt32(tokens_n[0]);
        int m = Convert.ToInt32(tokens_n[1]);
        string[] c_temp = Console.ReadLine().Split(' ');
        long[] c = Array.ConvertAll(c_temp,Int64.Parse);
        // Print the number of ways of making change for 'n' units using coins having the values given by 'c'
        long ways = getWays(n, c);
    }
}
​
9
  • 1
    Deixa ver se eu entendi. Você quer saber quantas combinações com os itens de b (podendo inclusive repetir um elemento) são possíveis para chegar ao valor de x? 7/05/2018 às 19:43
  • Ou você quer simplesmente somar os itens dentro do array? (pergunta só pra desencargo de consciencia, porque a do @DiegoRafaelSouza faz mais sentido)
    – Eric Wu
    7/05/2018 às 19:52
  • o que significa x ? 7/05/2018 às 19:53
  • 3
    Sinalizei. Rebaixei. 1) Sua edição muda completamente o escopo da pergunta. 2) A maior parte do conteúdo está em inglês. 3) Eu não acredito que alguém se proponha a resolver o seu desafio. 7/05/2018 às 20:25
  • 1
    @DiegoRafaelSouza Eu resolvi o que foi pedido na pergunta, mas o desafio dele provavelmente vai exigir performance, ou seja, o OP ainda terá que usar a cabeça se quiser vencer o tal desafio.
    – Gabriel
    11/05/2018 às 22:05

1 Resposta 1

2

O algoritmo que satisfaz o seu pedido é trivial de ser implementado. Segue um exemplo que escrevi:

// Essa função gera recursivamente toda a árvore de possibilidades para
// todos os trocos iguais ou menos que o objetivo.
static int GetWays(int objetivo, IEnumerable<int> moedas, int trocoParcial)
{
    // Se o troco parcial é o troco que procuramos, então este caminho
    // na árvore de possibilidades é uma resposta válida.
    if (trocoParcial == objetivo)
    {
        return 1;
    }

    // Se já não houver mais moedas ou se o troco parcial ultrapassar
    // o troco que procuramos, significa que esse caminho na árvore de
    // possibilidades não nos levou a uma resposta válida.
    if (!moedas.Any() || trocoParcial > objetivo)
    {
        return 0;
    }

    // Se não foi possível decidir se a resposta é ou não válida, temos
    // que recursivamente verificar as alternativas que seguem ambos os
    // galhos. Vamos somar todas as respostas válidas para todas as
    // possíveis alternativas que podemos tomar.:
    return GetWays(objetivo, moedas, trocoParcial + moedas.First()) + GetWays(objetivo, moedas.Skip(1), trocoParcial);
}

Coloquei vários comentários ao longo do código para ajudar na compreensão, apesar de que provavelmente não será necessário pois é um algoritmo bastante simplista. Tudo o que ele faz é gerar recursivamente todos os possíveis trocos, acumulando +1 caso o troco for válido (igual ao objetivo), ou +0 caso contrário.

Observando o código é possível rapidamente visualizar que esta função geraria uma árvore binária (a árvore de possibilidades). A árvore é binária porque a cada nodo não-terminal é feita uma escolha de 2 possibilidades:

  • A moeda é usada no troco; ou
  • A moeda não é usada no troco

Agora fica óbvio o trabalho feito em cada uma das chamadas recursivas e o porquê de haver exatamente duas chamadas.

No entanto, como exposto no texto em inglês que você colou na pergunta, essa implementação é extremamente ineficiente, pois toda a árvore de possibilidades é acumulada na stack do computador.

A análise da complexidade computacional da função acima será deixada como um exercício você resolver, caso tenha interesse (e eu recomendo fortemente que sim).

O texto em inglês ainda dá uma excelente dica de como evitar o acúmulo na stack. Você deve seguir a partir daí.

Eu te dei em mãos uma solução funcional. Agora você só precisa torná-la performática.

Espero que o meu código código e a minha explicação possam ajudar você e outros navegantes.

Abraço e boa sorte!

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .