Difference between revisions of "Problema do colecionador de moedas"

Revision as of 14:39, 24 September 2008

Dificuldade Única

Problema adaptado de http://www.topcoder.com/stat?c=problem_statement&pm=9933&rd=13506

Um colecionador de moedas tem o objetivo de colecionar o maior número possível de moedas diferentes (qualida ou valor não são importantes).

Faça um programa que recebendo um vetor V com o valor das moedas e um vetor C com as moedas que o colecionar possui informe qual o número máximo de moedas diferentes que o colecionador pode conseguir.

Considere que só é possível conseguir dinheiro para compra vendendo as moedas que possui.

Exemplo

Entrada

Vetor V
9 (o valor da moeda "0" é $9)
4 (o valor da moeda "1" é $4)
7 (o valor da moeda "2" é $7)
8 (o valor da moeda "3" é $8)
17 (o valor da moeda "4" é $17)

Vetor C
4
0

(O colecionador possui a moeda "0" e "4", que custam respectivamente $9 e $17 conforme consta no vetor V).

Saída

3