题解 | 购物单

#include <iostream>
using namespace std;
int max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
int dp(int i, int n, int* v, int* w, int* q, bool* visit, int m, int** DP) {
    //找到所有的主件和附件的组合
    //visit是否被买
    int a = 0;
    int b = 0;
    if (i > m - 1)
        return 0;
    if (visit[i]) {
        if (DP[i + 1][n] != -1) {
            return DP[i + 1][n];
        } else {
            if (DP[i + 1][n] == -1)
                DP[i + 1][n] = dp(i + 1, n, v, w, q, visit, m, DP);
            return DP[i + 1][n];
        }

    }
    if (q[i] == 0) {
        int r1 = 0, r2 = 0, r3 = 0, r4 = 0;
        int count = 0;
        int k = -1, l = -1;
        for (int j = i + 1; j < m; ++j) {
            if (q[j] - 1 == i) {
                if (count == 0) {
                    k = j;
                    count++;
                } else {
                    l = j;
                    count++;
                }
            }
        }
        if (count == 0) {
            visit[i] = true;
            a = dp(i + 1, n, v, w, q, visit, m, DP);
            if (v[i] <= n) {
                if (DP[i + 1][n - v[i]] != -1) {
                    b = v[i] * w[i] + DP[i + 1][n - v[i]];
                } else {
                    DP[i + 1][n - v[i]] = dp(i + 1, n - v[i], v, w, q, visit, m, DP);
                    b = v[i] * w[i] + DP[i + 1][n - v[i]];
                }
            }
            visit[i] = false;
            return max(a, b);
        } else if (count == 1) {
            visit[i] = true;
            visit[k] = true;
            if (v[i] <= n) {
                if (DP[i + 1][n] == -1) {
                    DP[i + 1][n] = dp(i + 1, n, v, w, q, visit, m, DP);
                }
                if (DP[i + 1][n - v[i]] == -1) {
                    DP[i + 1][n - v[i]] = dp(i + 1, n - v[i],
                                             v, w, q, visit, m, DP);
                }
                r1 = max(DP[i + 1][n], b = v[i] * w[i] + DP[i + 1][n - v[i]]);
                if (v[i] + v[k] <= n) {
                    if (DP[i  + 1][n - v[i] - v[k]] == -1) {
                        DP[i  + 1][n - v[i] - v[k]] = dp(i + 1, n - v[i] - v[k],
                                                         v, w, q, visit, m, DP);
                    }
                    r2 = v[i] * w[i] + v[k] * w[k] + DP[i  + 1][n - v[i] - v[k]];
                }
            }
            visit[i] = false;
            visit[k] = false;
            return max(r1, r2);
        } else if (count == 2) {
            visit[i] = true;
            visit[k] = true;
            visit[l] = true;
            if (v[i] <= n) {
                if (DP[i + 1][n] == -1) {
                    DP[i + 1][n] = dp(i + 1, n, v, w, q, visit, m, DP);
                }
                if (DP[i + 1][n - v[i]] == -1) {
                    DP[i + 1][n - v[i]] = dp(i + 1,
                                             n - v[i],
                                             v, w, q, visit, m, DP);
                }
                r1 = max(DP[i + 1][n], v[i] * w[i] + DP[i + 1][n - v[i]]);
                if (v[i] + v[k] <= n) {
                    if (DP[i + 1][n - v[i] - v[k]] == -1)
                        DP[i + 1][n - v[i] - v[k]] = dp(i + 1, n - v[i] - v[k],
                                                        v, w, q, visit, m, DP);
                    r2 = v[i] * w[i] + v[k] * w[k] + DP[i + 1][n - v[i] - v[k]];
                }
                if (v[i] + v[l] <= n) {
                    if (DP[i + 1][n - v[i] - v[l]] == -1)
                        DP[i + 1][n - v[i] - v[l]] = dp(i + 1, n - v[i] - v[l],
                                                        v, w, q, visit, m, DP);
                    r3 = v[i] * w[i] + v[l] * w[l] + DP[i + 1][n - v[i] - v[l]];
                }
                if (v[i] + v[k] + v[l] <= n) {
                    if (DP[i + 1][n - v[i] - v[k] - v[l]] == -1)
                        DP[i + 1][n - v[i] - v[k] - v[l]] = dp(i + 1, n - v[i] - v[k] - v[l],
                                                               v, w, q, visit, m, DP);
                    r4 = v[i] * w[i] + v[k] * w[k] + v[l] * w[l] + DP[i + 1][n - v[i] - v[k] -
                            v[l]];
                }
            }
            visit[i] = false;
            visit[k] = false;
            visit[l] = false;
            return max(max(r1, r2), max(r3, r4));
        }
    } else {
        int r1 = 0, r2 = 0, r3 = 0, r4 = 0;
        int count = 1;
        int k = q[i] - 1;
        int l = -1;
        for (int j = i; j < m; ++j) {
            if (q[j] - 1 == k) {
                l = j;
                count++;
                break;
            }
        }
        if (count == 1) {
            visit[k] = true;
            visit[i] = true;
            if (v[k] <= n) {
                if (DP[i + 1][n] == -1)
                    DP[i + 1][n] = dp(i + 1, n, v, w, q, visit, m, DP);
                if (DP[i + 1][n - v[k]] == -1)
                    DP[i + 1][n - v[k]] = dp(i + 1,
                                             n - v[k],
                                             v, w, q, visit, m, DP);
                r1 = max(DP[i + 1][n], DP[i + 1][n - v[k]]);
                if (v[i] + v[k] <= n) {
                    if (DP[i + 1][n - v[i] - v[k]] == -1)
                        DP[i + 1][n - v[i] - v[k]] = dp(i + 1, n - v[i] - v[k],
                                                        v, w, q, visit, m, DP);
                    r2 = v[i] * w[i] + v[k] * w[k] + DP[i + 1][n - v[i] - v[k]];
                }
            }
            visit[k] = false;
            visit[i] = false;
            return max(r1, r2);
        } else if (count == 2) {
            visit[k] = true;
            visit[i] = true;
            visit[l] = true;
            if (v[k] <= n) {
                if (DP[i + 1][n] == -1)
                    DP[i + 1][n] = dp(i + 1, n, v, w, q, visit, m, DP);
                if (DP[i + 1][n - v[k]] == -1)
                    DP[i + 1][n - v[k]] = dp(i + 1,
                                             n - v[k],
                                             v, w, q, visit, m, DP);
                r1 = max(DP[i + 1][n], v[k] * w[k] + DP[i + 1][n - v[k]]);
                if (v[i] + v[k] <= n) {
                    if (DP[i + 1][n - v[i] - v[k]] == -1)
                        DP[i + 1][n - v[i] - v[k]] = dp(i + 1, n - v[i] - v[k],
                                                        v, w, q, visit, m, DP);
                    r2 = v[i] * w[i] + v[k] * w[k] + DP[i + 1][n - v[i] - v[k]];
                }
                if (v[k] + v[l] <= n) {
                    if (DP[i + 1][n - v[k] - v[l]] == -1)
                        DP[i + 1][n - v[k] - v[l]] = dp(i + 1, n - v[k] - v[l],
                                                        v, w, q, visit, m, DP);
                    r3 = v[k] * w[k] + v[l] * w[l] + DP[i + 1][n - v[k] - v[l]];
                }
                if (v[i] + v[k] + v[l] <= n) {
                    if (DP[i + 1][n -  v[i] - v[k] - v[l]] == -1)
                        DP[i + 1][n -  v[i] - v[k] - v[l]] = dp(i + 1, n -v[i] - v[k] - v[l],
                                                                v, w, q, visit, m, DP);
                    r4 = v[i] * w[i] + v[k] * w[k] + v[l] * w[l] + DP[i + 1][n -  v[i] - v[k] -
                            v[l]];
                }
            }
            visit[k] = false;
            visit[i] = false;
            visit[l] = false;
            return max(max(r1, r2), max(r3, r4));
        }
    }
    return 0;
}
int main() {
    int m, n;
    cin >> n >> m;
    int* v = new int [m];
    int* w = new int [m];
    int* q = new int [m];
    bool* visit = new bool [m];
    int** DP = new int* [m + 1];
    for (int i = 0; i < m + 1; ++i)
        DP[i] = new int [n + 1];
    for (int i = 0; i < m + 1; ++i)
        for (int j = 0; j < n + 1; ++j)
            DP[i][j] = -1;
    for (int i = 0; i < m; ++i) {
        cin >> v[i] >> w[i] >> q[i];
        visit[i] = false;
    }
    cout << dp(0, n, v, w, q, visit, m, DP);
}
// 64 位输出请用 printf("%lld")