找更多硬币

https://www.acwing.com/problem/content/description/1556/

思路：
01背包问题的经典模型，这不过这儿的属性是bool，表示能不能，而且要你输出方案，由于方案要字典序最小，所以Ai则是能选则选，又由于是从后往前推的，所以这也暗示我们a数组要按从大到小的顺序排序。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, M = 110;

int n, m;
int a[N];
bool f[N][M];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    sort(a + 1, a + n + 1, greater<int>());

    f[0][0] = true;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if (j >= a[i]) f[i][j] |= f[i - 1][j - a[i]];
        }

    if (!f[n][m]) puts("No Solution");
    else
    {
        bool is_first = true;
        while (n)
        {
            if (m >= a[n] && f[n - 1][m - a[n]])
            {
                if (is_first) is_first = false;
                else cout << ' ';
                cout << a[n];
                m -= a[n];
            }

            n -- ;
        }
    }

    return 0;
}