Switch to full style
Todas as dúvidas que tenha sobre arranjos simples, completos, combinações ou probabilidades
Responder

Achar elementos que compõem um determinado número.

27 nov 2013, 17:52

Olá pessoal,

Estou com uma dúvida e queria ver se alguém conhece algum método matemático que soluciona a minha questão:

Tenho um número X e dentro de um conjunto formado por quatro números, quero ver quais destes quatro elementos podem formar o número X.

Exemplo:

X = 122

A B C D
Elementos {100, 50, 22, 43}

Somente visualizando sabemos que os elementos A e C podem formar o número X.

Obrigado!

Re: Achar elementos que compõem um determinado número.

27 nov 2013, 20:31

Olá boa tarde,

Esse é um problema interessante. Se a quantidade de números no conjunto for muito grande pode ser oneroso resolvê-lo, pois haveria a necessidade de se fazer todas as combinações possíveis dos elementos do conjunto ( isso dá \(2^n\) subconjuntos onde \(n\) é a quantidade de elementos no conjunto ), efetuar a soma de cada subconjunto e verificar se casa com um valor dado.

Essa questão é um caso especial do Problema da Mochila. Então uma forma de abordar a solução seria usar um algoritmo de programação dinâmica (preferencialmente). Obviamente, podem ocorrer casos que não conseguimos encher totalmente a mochila, que no caso dessa questão seria obter os elementos do conjunto cuja soma é exatamente o valor dado.
Responder