Solução por Rogério Júnior
Este é um problema clássico de Programação Dinâmica. Assim como no Knapsack (com solução aqui), ou Pontes de São Petesburgo (com solução aqui), vamos testar todas as possibilidades olhando, para cada moeda, se ela deve ou não ser inserida no troco. Vamos criar uma tabela de PD int matriz[1010][100010] que guardará os estados já calculados, e usaremos uma função recursiva de nome busca para calcularmos todos os estados na abordagem Top-Down. Vamos salvar o valor de cada moeda no vetor int moeda[1010], e guardar o char resposta que começará com valor 'N'.
A função será bem simples: ela receberá a moeda que estamos olhando (int coin) e soma que já temos das moedas passadas que colocamos no troco (int soma). Se já tivermos calculado a PD para tal estado, a função retorna. Caso contrário, marcamos esse estado na tabela de PD. Verificamos agora se soma já é o valor desejado (soma==n). Se for, fazemos a variável resposta receber 'S' e retornamos a função. Se não for ainda, continuamos a função. Se já tivermos olhado todas as moedas (coin >n) ou a soma já tiver superado o valor desejado (soma>v), a função retorna. Caso contrário, chamamos a função colocando e não colocando a moeda: colocar é chamar para a próxima moeda adicionando o valor da atual a soma ("busca(coin+1, soma+moeda[coin]);") e não colocar é chamar para a próxima com a mesma soma que tínhamos na atua ("busca(coin+1, soma);").
Se chamarmos a função para a primeira moeda, ela testa todos os casos necessários. Se em algum momento tivermos encontrado um conjunto de moedas com o valor desejado, a variável resposta terá o valor 'S' e, caso contrário, não terá sido alterada e ainda guardará o valor 'N'. Logo, basta imprimí-la. Segue o código comentado para melhor entendimento.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| char resposta='N'; | |
| int v, m; | |
| bool matriz[1010][100010]; | |
| int moeda[1010]; | |
| void busca(int coin, int soma) // função recursiva da PD Top-Down | |
| { | |
| if(matriz[coin][soma]) return; // se já tivermos calculado esse estado da PD, a função retorna | |
| matriz[coin][soma]=1; // marcamos o estado atual como calculado | |
| if(soma==v) // se a soma for o valor desejado | |
| { | |
| resposta='S'; // resposta recebe 'S' | |
| return; // e a função retorna | |
| } | |
| // Se játivermos t=olhado todas as moedas, ou superado a soma desejada | |
| if(coin>m || soma>v) return; // a função retorna | |
| busca(coin+1, soma+moeda[coin]); // testamos todas a possibilidades com a moeda atual | |
| busca(coin+1, soma); // testamos todas a possibilidades sem a moeda atual | |
| } | |
| int main () | |
| { | |
| scanf("%d %d", &v, &m); // lemos os valores de v e m | |
| for(int i=1; i<=m; i++) scanf("%d", &moeda[i]); // lemos os valores de cada moeda | |
| busca(1, 0); // chamamos a função da PD | |
| printf("%c\n", resposta); // imprimimos a resposta seguida de quebra de linha | |
| return 0; | |
| } |