本题为典型的多维背包问题，要求在满足多个资源限制条件下最大化价值，并输出选取物品的具体方案。由于状态维度较高（四维容量+一维物品），直接使用五维数组进行动态规划极易导致内存超限，因此需要采用数据类型优化或滚动数组等技巧来降低空间消耗。

题目输入包含 n 个物品，每个物品具有五项属性：四种资源消耗量 p, a, c, m 和对应的价值 g。目标是在给定的四种资源上限 P, A, C, M 下，选择若干物品使得总价值最大，并按编号升序输出所选物品的索引（从0开始）。

方法一：short 类型优化的五维 DP

考虑到单个状态值不会过大，可将 dp 数组定义为 short 类型以节省空间。同时使用 vis 数组记录转移路径。状态转移方程如下：

dp[i][j][k][l][t] = max(dp[i-1][j][k][l][t], dp[i-1][j-p[i]][k-a[i]][l-c[i]][t-m[i]] + g[i])

若更新发生，则标记 vis[i][j][k][l][t] = true。最终从最大价值状态反向追踪 vis 标记，还原出选取序列。

代码实现（short 优化版）

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

typedef short s;
s n, P, A, C, M;
s p[37], a[37], c[37], m[37], g[37];
s dp[37][37][37][37][37];
bool vis[37][37][37][37][37];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> p[i] >> a[i] >> c[i] >> m[i] >> g[i];
    cin >> P >> A >> C >> M;

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= P; ++j)
            for (int k = 0; k <= A; ++k)
                for (int l = 0; l <= C; ++l)
                    for (int t = 0; t <= M; ++t) {
                        dp[i][j][k][l][t] = dp[i-1][j][k][l][t];
                        if (j >= p[i] && k >= a[i] && l >= c[i] && t >= m[i]) {
                            s val = dp[i-1][j-p[i]][k-a[i]][l-c[i]][t-m[i]] + g[i];
                            if (val > dp[i][j][k][l][t]) {
                                dp[i][j][k][l][t] = val;
                                vis[i][j][k][l][t] = true;
                            }
                        }
                    }

    s best_j = 0, best_k = 0, best_l = 0, best_t = 0;
    s max_val = 0;
    for (int j = 0; j <= P; ++j)
        for (int k = 0; k <= A; ++k)
            for (int l = 0; l <= C; ++l)
                for (int t = 0; t <= M; ++t)
                    if (dp[n][j][k][l][t] > max_val) {
                        max_val = dp[n][j][k][l][t];
                        best_j = j; best_k = k; best_l = l; best_t = t;
                    }

    vector<int> path;
    for (int i = n; i >= 1; --i) {
        if (vis[i][best_j][best_k][best_l][best_t]) {
            path.push_back(i - 1);
            best_j -= p[i];
            best_k -= a[i];
            best_l -= c[i];
            best_t -= m[i];
        }
    }

    cout << path.size() << endl;
    for (int i = path.size() - 1; i >= 0; --i)
        cout << path[i] << " ";
    cout << endl;

    return 0;
}

方法二：滚动数组优化空间

利用完全背包的倒序遍历思想，将第一维压缩掉，仅保留四维状态数组。此时需额外保存完整的 vis 矩阵用于路径回溯。状态转移改为从高容量向低容量迭代，避免重复使用同一物品。

代码实现（滚动数组版）

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

short n, P, A, C, M;
short p[37], a[37], c[37], m[37], g[37];
short dp[37][37][37][37];
bool used[37][37][37][37][37]; // used[i][j][k][l][o]: 第i个物品是否在状态(j,k,l,o)中被选用

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> p[i] >> a[i] >> c[i] >> m[i] >> g[i];
    cin >> P >> A >> C >> M;

    memset(dp, 0, sizeof(dp));
    memset(used, 0, sizeof(used));

    for (int i = 1; i <= n; ++i)
        for (int j = P; j >= p[i]; --j)
            for (int k = A; k >= a[i]; --k)
                for (int l = C; l >= c[i]; --l)
                    for (int o = M; o >= m[i]; --o) {
                        short prev = dp[j - p[i]][k - a[i]][l - c[i]][o - m[i]];
                        if (prev + g[i] >= dp[j][k][l][o]) {
                            dp[j][k][l][o] = prev + g[i];
                            used[i][j][k][l][o] = true;
                        }
                    }

    vector<int> selected;
    int cur_p = P, cur_a = A, cur_c = C, cur_m = M;
    for (int i = n; i >= 1; --i) {
        if (used[i][cur_p][cur_a][cur_c][cur_m]) {
            selected.push_back(i - 1);
            cur_p -= p[i];
            cur_a -= a[i];
            cur_c -= c[i];
            cur_m -= m[i];
        }
    }

    cout << selected.size() << endl;
    for (int i = selected.size() - 1; i >= 0; --i)
        cout << selected[i] << " ";
    cout << endl;

    return 0;
}