Array
(
)

duvida montagem de algoritmo

Zumbi
   - 23 fev 2006

Galera, será que alguem poderia me ajudar nesse problema?

tenho uma lista com valores por exemplo, [2,3,4,7,8,10]

e tenho um valor que é = 31

como eu poderia fazer uma divisão para chegar em um resultado parecido com esse, 3 valores 7 e 1 valor 10

no caso seria quais e quantas vezes eu teria que usar um elemento da lista para igualar um valor.[/img]


Motta
   - 23 fev 2006

Uma variante do knapsack

Todas as possibilidades devem ser tentadas :

Começe de tras para frente se o ultimo valor do array (é sempre crescente ?) for maior que o valor requerido vá para o seguinte
se for menor veja o menor multiplo que seja menor ou igual ao valor , va para o prximo eaplique a lógica de novo , depois faça isto para o multiplo anterior do ultimo valor do array e assim por diante.

ficou claro ,acho que não ....

2 x 10 + 1 x 8 + 1 X 3 = 31 tb é solução

forum legal para isto :
http://forum.imasters.com.br/index.php?showforum=117

um site :
http://www.nist.gov/dads/