采用一个数组g来滚动更新当前体积的最小序列

初始C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int M = 105;
int dp[M];
vector<int> g[M];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin >> n >> m;
    vector<int> ai(n + 1,0);
    for(int i = 1; i <= n; i++) cin >> ai[i];
    sort(ai.begin() + 1,ai.end());
    dp[0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = m; j >= ai[i]; j--){
            int t = dp[j];
            dp[j] += dp[j - ai[i]];
            if(dp[j] != 0){
                if(t == 0){
                    g[j] = g[j - ai[i]];
                    g[j].push_back(ai[i]);
                }else if(t != 0){
                    vector<int> temp = g[j - ai[i]];
                    temp.push_back(ai[i]);
                    if(temp < g[j]){
                        g[j] = temp;
                    }
                }
            }
        }
    }
    if(dp[m] == 0) cout << "No Solution";
    else    for(int i = 0; i < g[m].size(); i++) cout << g[m][i] << " ";
    cout << "\n";
    return 0;
}

但是这个初始代码版本最后两个点超时了，因为在不断更新g[j]的时候要比较两个字典序的大小，频繁的vector复制导致时间复杂度过不了最后两个测试点，下面是优化版本

最终c++代码如下

#include<bits/stdc++.h>
using namespace std;

const int M = 105;

struct Seq {
    int data[105]; // 存储硬币面额序列
    int size;      // 序列长度
    Seq() : size(0) {}
};

int dp[M];
Seq g[M];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> ai(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> ai[i];
    sort(ai.begin() + 1, ai.end());

    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= ai[i]; j--) {
            if (dp[j - ai[i]] == 0) continue;
            int t = dp[j];
            dp[j] += dp[j - ai[i]];
            if (dp[j] != 0) {
                if (t == 0) {
                    // 首次找到j的组合，直接复制并添加当前硬币
                    memcpy(g[j].data, g[j - ai[i]].data, sizeof(int) * g[j - ai[i]].size);
                    g[j].size = g[j - ai[i]].size;
                    g[j].data[g[j].size++] = ai[i];
                } else {
                    // 构造新序列
                    Seq temp;
                    temp.size = g[j - ai[i]].size + 1;
                    memcpy(temp.data, g[j - ai[i]].data, sizeof(int) * g[j - ai[i]].size);
                    temp.data[g[j - ai[i]].size] = ai[i];

                    // 比较字典序
                    bool replace = false;
                    int min_len = min(temp.size, g[j].size);
                    int k;
                    for (k = 0; k < min_len; k++) {
                        if (temp.data[k] < g[j].data[k]) {
                            replace = true;
                            break;
                        } else if (temp.data[k] > g[j].data[k]) {
                            break;
                        }
                    }
                    // 处理前缀情况
                    if (!replace) {
                        if (k == temp.size && temp.size < g[j].size) {
                            replace = true;
                        }
                    }
                    if (replace) {
                        memcpy(g[j].data, temp.data, sizeof(int) * temp.size);
                        g[j].size = temp.size;
                    }
                }
            }
        }
    }

    if (dp[m] == 0) {
        cout << "No Solution";
    } else {
        for (int i = 0; i < g[m].size; i++) {
            cout << g[m].data[i] << (i == g[m].size - 1 ? "\n" : " ");
        }
    }
    return 0;
}