思路与算法

令dp[v]表示已处理组、容量至多v的最大价值。逐组先复制旧数组，再枚举本组每件物品，从旧数组转移到新数组；复制保留整组不选的方案。

正确性说明

对已处理组数归纳。最优方案在新组中或者不选，或者恰选某一件。前者由复制覆盖；后者去掉该件后是上一组的合法子方案，旧数组转移覆盖且不会再次选本组物品，因此转移恰好枚举全部合法方案。

复杂度

设T组、N件、容量V。数组初始化及各组复制O(TV)，所有物品转移O(NV)，总O((T+N)V)，空间O(V+N+T)。

易错点

同组转移必须读取旧数组；允许空组、容量0和物品过重。价值及答案用64位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int V, n, T;
    cin >> V >> n >> T;
    vector<vector<pair<int, long long>>> group(T + 1);
    for (int i = 0, w, p; i < n; i++) {
        long long c;
        cin >> w >> c >> p;
        group[p].push_back({w, c});
    }
    vector<long long> dp(V + 1);
    for (int p = 1; p <= T; p++) {
        auto old = dp;
        for (int cap = 0; cap <= V; cap++)
            for (auto item : group[p])
                if (item.first <= cap)
                    dp[cap] = max(dp[cap], old[cap - item.first] + item.second);
    }
    cout << dp[V] << '\n';
}