题目描述

C++代码

样例

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1e4 + 10;
int a[N];
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> f(n + 1, vector<int>(m + 1, -1));
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n, [](const int& a, const int& b) { return a > b; });
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if (a[i] <= j)
            {
                f[i][j] = max(f[i][j], f[i - 1][j - a[i]] + a[i]);
            }
        }
    }
    if (f[n][m] != m) {
        cout << "No Solution";
    }
    else {
        int pos = m;
        bool vis = true;
        for (int i = n; i >= 1 && pos > 0; i--)
        {
            if (pos >= a[i] && f[i][pos] == f[i - 1][pos - a[i]] + a[i])
            {
                if (vis) {
                    cout << a[i];
                    vis = false;
                }
                else cout << " " << a[i];
                pos -= a[i];
            }
        }
    }
    return 0;
}