Problema

Eva adora colecionar moedas de todo o universo, incluindo outros planetas como Marte. Um dia, ela visitou um shopping universal que aceitava todos os tipos de moedas como pagamento. No entanto, havia um requisito especial: para cada conta, ela deve pagar o valor exato. Como ela tem até 10^4 moedas, ela definitivamente precisa da sua ajuda. Você deve dizer a ela, para qualquer valor dado de dinheiro, se ela pode encontrar algumas moedas para pagá-lo.

Especificação de Entrada

Cada arquivo de entrada contém um caso de teste. Para cada caso, a primeira linha contém dois números positivos: N (<=10^4, o número total de moedas) e M (<=10^2, o valor que Eva deve pagar). A segunda linha contém N valores nominais das moedas, que são todos números positivos. Todos os números em uma linha são separados por um espaço.

Especificação de Saída

Para cada caso de teste, imprima em uma linha os valores nominais V1 <= V2 <= … <= Vk tal que V1 + V2 + … + Vk = M. Todos os números devem ser separados por um espaço, e não deve haver espaço extra no final da linha. Se tal solução não for única, saída a menor sequência. Se não houver solução, saída "No Solution".

Nota: uma sequência {A[1], A[2], …} é dita "menor" que a sequência {B[1], B[2], …} se existir k >= 1 tal que A[i]=B[i] para todos i < k, e A[k] < B[k].

Exemplo de Entrada 1

8 9
5 9 8 7 2 3 4 1

Exemplo de Saída 1

1 3 5

Exemplo de Entrada 2

4 8
7 2 4 3

Exemplo de Saída 2

No Solution

Análise do Problema

O objetivo é selecionar um subconjunto de moedas com valor nominal fornecido que some exatamente ao valor alvo M. A saída deve ser a sequência lexicograficamente menor dos valores nominais em ordem crescente. Dois desafios principais surgem: primeiro, determinar se existe uma combinação válida; segundo, se múltiplas soluções existem, identificar a sequência com a menor ordem lexicográfica.

A abordagem para o primeiro desafio baseia-se no problema da mochila 0/1. Definimos uma tabela de programação dinâmica (DP) onde dp[i][j] indica se é possível obter o valor j usando um subconjunto das primeiras i moedas. A recorrência é:

• Não incluir a moeda i: dp[i][j] = dp[i-1][j]
• Incluir a moeda i, se j >= valor da moeda i: dp[i][j] = dp[i][j] ou dp[i-1][j - valor_moeda_i]

O valor dp[N][M] indica se uma solução existe.

Para o segundo desafio, a sequência lexicograficamente menor é garantida ordenando as moedas em ordem decrescente. Durante o retrocesso na tabela DP, percorremos as moedas de trás para frente. Se ao considerar a moeda k, a condição M >= valor_moeda_k e dp[k-1][M - valor_moeda_k] for verdadeira, a moeda é incluída na solução, e o valor alvo é reduzido. Esse processo garante que as menores moedas sejam selecionadas primeiro, resultando na sequência ordenada crescentemente desejada.

Solução 1: Programação Dinâmica com Tabela 2D e Retrocesso

Esta implementação utiliza uma tabela DP bidimensional e ordena as moedas em ordem decrescente para facilitar a seleção da sequência menor.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int quantidade_moedas, valor_alvo;
    cin >> quantidade_moedas >> valor_alvo;

    vector<int> moedas(quantidade_moedas + 1); // 1-indexado
    for (int i = 1; i <= quantidade_moedas; i++) {
        cin >> moedas[i];
    }

    // Ordena em ordem decrescente para garantir a menor sequência
    sort(moedas.begin() + 1, moedas.end(), greater<int>());

    // Tabela DP: dp[i][j] indica se o valor j pode ser formado com as primeiras i moedas
    vector<vector<bool>> tabela_dp(quantidade_moedas + 1, vector<bool>(valor_alvo + 1, false));
    tabela_dp[0][0] = true;

    for (int i = 1; i <= quantidade_moedas; i++) {
        for (int j = 0; j <= valor_alvo; j++) {
            tabela_dp[i][j] = tabela_dp[i-1][j];
            if (j >= moedas[i] && tabela_dp[i-1][j - moedas[i]]) {
                tabela_dp[i][j] = true;
            }
        }
    }

    if (!tabela_dp[quantidade_moedas][valor_alvo]) {
        cout << "No Solution";
    } else {
        vector<int> resultado;
        int indice_moeda = quantidade_moedas;
        int valor_restante = valor_alvo;

        while (indice_moeda > 0) {
            if (valor_restante >= moedas[indice_moeda] && tabela_dp[indice_moeda - 1][valor_restante - moedas[indice_moeda]]) {
                resultado.push_back(moedas[indice_moeda]);
                valor_restante -= moedas[indice_moeda];
            }
            indice_moeda--;
        }

        // Saída em ordem crescente (já coletado do menor para o maior)
        for (size_t i = 0; i < resultado.size(); i++) {
            if (i > 0) cout << " ";
            cout << resultado[i];
        }
    }

    return 0;
}

Solução 2: Programação Dinâmica Otimizada com Tabela 1D e Matriz de Escolha

Esta variante utiliza uma tabela DP unidimensional para economizar espaço e uma matriz auxiliar para rastrear as escolhas durante o retrocesso.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int num_moedas, alvo;
    scanf("%d%d", &num_moedas, &alvo);

    vector<int> valores(num_moedas + 1);
    for (int i = 1; i <= num_moedas; i++) {
        scanf("%d", &valores[i]);
    }

    // Ordena em ordem decrescente
    sort(valores.begin() + 1, valores.end(), greater<int>());

    vector<int> dp(alvo + 1, 0); // dp[j] armazena o maior valor possível até j
    vector<vector<bool>> escolha(num_moedas + 1, vector<bool>(alvo + 1, false));

    for (int i = 1; i <= num_moedas; i++) {
        for (int j = alvo; j >= valores[i]; j--) {
            if (dp[j] <= dp[j - valores[i]] + valores[i]) {
                escolha[i][j] = true;
                dp[j] = dp[j - valores[i]] + valores[i];
            }
        }
    }

    if (dp[alvo] != alvo) {
        printf("No Solution");
    } else {
        vector<int> moedas_selecionadas;
        int valor_corrente = alvo;
        int idx = num_moedas;

        while (valor_corrente > 0) {
            if (escolha[idx][valor_corrente]) {
                moedas_selecionadas.push_back(valores[idx]);
                valor_corrente -= valores[idx];
            }
            idx--;
        }

        // A saída já está em ordem crescente devido à coleta retrocedente
        for (size_t i = 0; i < moedas_selecionadas.size(); i++) {
            if (i > 0) printf(" ");
            printf("%d", moedas_selecionadas[i]);
        }
    }

    return 0;
}