python/C++专题课程/背包九讲/TestProject/8_GeneralizationPackage.cpp

#include <bits/stdc++.h>

using namespace std;
/**
 8. 泛化物品
 ）题目：
    在背包容量为v的背包问题中，泛化物品是一个定义域为0..v中的整数的函数h，当分配给它的费用为v时，能得到的价值就是h(v)。
    为了应用泛化物品思想，这里假设题目为：存在依赖关系树（简单起见，只有一个根节点），即有依赖的物品也可以被依赖，可结合原文7.3节来理解此句。
2）输入：
    测试用例数
        物品数 背包容量 根节点编号
        第i个物品的ci wi di(依赖物品的编号，-1为不依赖其他物品)
 * @return
 */
#define maxN 100
#define maxV 1000

int n, v;
int cnt = 0;
int head[maxN];
int wi[maxN], ci[maxN];
int f[maxN][maxV];

struct Edge {
    int v, next;
} e[maxN - 1];

void addEdge(int u, int v) {
    e[cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

void treeDP(int u) {
    for (int i = ci[u]; i <= v; i++) {
        f[u][i] = wi[u];
    }
    for (int i = head[u]; i != -1; i = e[i].next) {
        int curr = e[i].v;
        treeDP(curr);
        for (int j = v; j >= 0; j--) {
            for (int k = j - ci[u]; k >= 0; k--) {
                f[u][j] = max(f[u][j], f[u][j - k] + f[curr][k]);
            }
        }
    }
}

int main(void) {
    int cases, root;
    freopen("../8.txt", "r", stdin);
    cin >> cases;
    while (cases--) {
        cnt = 0;
        memset(head, -1, sizeof(head));
        memset(f, 0, sizeof(f));
        cin >> n >> v >> root;
        for (int i = 0; i < n; i++) {
            int di;
            cin >> ci[i] >> wi[i] >> di;
            addEdge(di, i);
        }
        treeDP(root);
        cout << f[root][v] << endl;
    }
}