题目描述

有 N 个物品和一个容量是 V 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。

接下来有 N 行数据，每行数据表示一个物品。
第 i 行有三个整数 vi,wi,pi，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 pi=−1，表示根节点。 数据保证所有物品构成一棵树。

输出格式
输出一个整数，表示最大价值。

数据范围
1≤N,V≤100
1≤vi,wi≤100
父节点编号范围：

内部结点：1≤pi≤N;
根节点 pi=−1;

样例

输入样例
5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2
输出样例：
11

为什么是背包问题啊？？？视频看了也懵懵的，y总评论区的一句话却让我茅塞顿开：

啊这里对于树中的每个节点来说，就是一个分组背包问题。每个子节点是一组物品，
每个子节点的不同体积和每个体积所对应的最大价值，就是这个物品组中的物品。

C++ 代码（徐持衡的）

#include<iostream>
#include<vector>

int N, V;
int v[107], w[107];
std::vector<int>pa[107];
int dp[107][107] = { {} };

void DFS(int now)
{
    for (int i = 0; i < pa[now].size(); i++)
    {
        int son = pa[now][i];
        for (int j = 0; j <= V; j++)
            dp[son][j] = dp[now][j] + w[son];
        DFS(son);
        for (int j = v[son]; j <= V; j++)
            if (dp[son][j - v[son]] > dp[now][j])
                dp[now][j] = dp[son][j - v[son]];
    }
    return;
}

int main(void)
{
    std::ios_base::sync_with_stdio(false);
    std::cin >> N >> V;
    for (int i = 1; i <= N; i++)
    {
        int p;
        std::cin >> v[i] >> w[i] >> p;
        if (-1 == p)p = 0;
        pa[p].push_back(i);
    }
    DFS(0);
    std::cout << dp[0][V];
    return 0;
}

做金明的预算方案超时发现上面的代码

超时代码如下，只过七个小数据的测试点

思考：
dp_left_max数组记录的是给该组v体积，最多可以获得多少的回报，dp表示给该组以及之前
各组体积一共v，若给该组left体积，给之前v-left体积可以获得最大收入，递推应该求出给该
组多少体积才是最优解，超时了因为用了两个dp，并且这里不需要枚举体积，枚举方案即可，欸！！！
而上述的代码将dp[i][j]表示为若到了该结点还剩下j体积情况下的最优解，如此：当要更新
父节点的值的时候，只要比较当父节点还剩下j体积时，若给出部分体积给该子结点，是否可以
获得更大的值，如果可以，那么该父结点的值更新，
再次遍历到下一个子结点的时候，再把涵盖了前一个子结点的最优解的值带入该子结点，dp意义
与上面一样，而前面的解包括了若还剩xx体积就可以加入前面若干个结点的最优解，以此推出当
根节点还剩V体积时的最优解；

#include<iostream>
#include<algorithm>
#include<vector>

std::vector<int>head[60 + 7];
int money[60 + 7] = {}, imp[60 + 7] = {};
int pre[60 + 7] = {}, now = 1;
int now_idx = 1, master = 0;
int N, M; //其中N表示总钱数，M为希望购买物品的个数
int dp[60 + 7][32000 + 7] = { {} };
int dp_left_max[60 + 7][32000 + 7] = { {} };

void painting(int dp[60 + 7][32000 + 7])
{
    for (int group = 1; group <= master; group++)
    {
        while (pre[now])now++;
        for (int i = money[now]; i <= N; i++)
        {
                dp[group][i] = money[now] * imp[now];
                int lea = i - money[now];
                if (head[now].size())
                {
                    if (head[now].size() == 1)
                    {
                        if (lea >= money[head[now][0]])
                            dp[group][i] += money[head[now][0]] * imp[head[now][0]];
                    }
                    else
                    {
                        if (lea >= money[head[now][0]] + money[head[now][1]])
                            dp[group][i] += money[head[now][0]] * imp[head[now][0]] + money[head[now][1]] * imp[head[now][1]];
                        else if (lea >= money[head[now][0]] && lea < money[head[now][1]])
                            dp[group][i] += money[head[now][0]] * imp[head[now][0]];
                        else if (lea < money[head[now][0]] && lea >= money[head[now][1]])
                            dp[group][i] += money[head[now][1]] * imp[head[now][1]];
                        else if (lea >= money[head[now][0]] && lea >= money[head[now][1]])
                            dp[group][i] += std::max(money[head[now][0]] * imp[head[now][0]], money[head[now][1]] * imp[head[now][1]]);
                    }
                }
        }
        now++;
    }
}

int main(void)
{
    std::ios_base::sync_with_stdio(false);
    std::cin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        int v, p, q;
        //v表示该物品的价格，p表示该物品的重要度（1~5），q表示该物品是主件还是附件
        //如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号。
        std::cin >> v >> p >> q;
        money[i] = v, imp[i] = p;
        if (q)
        {
            pre[i] = 1;
            head[q].push_back(i);
        }
        else master++;
    }
    painting(dp_left_max);
    now = 1;
    for (int group = 1; group <= master; group++)
    {
        while (pre[now])now++;
        for (int i = 0; i <= N; i++)
        {
            if (i >= money[now])
                for (int left = 0; left <= i; left++)
                    dp[group][i] = std::max(dp[group][i], dp[group - 1][i - left] + dp_left_max[group][left]);
            else dp[group][i] = dp[group - 1][i];

        }
        now++;
    }

    std::cout << dp[master][N];
    return 0;
}

算法二

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>

struct kk
{
    int v, w;
}ali[107];
std::vector<int>love[107];
int N, V, root = -1;
int dp[107][107] = { {} };//dp[i][j]表示当前i物品中，一共有j体积，与上面简便方法还剩j体积不一致；

void DFS(int now)
{
    for (int v = ali[now].v; v <= V; v++)dp[now][v] = ali[now].w;
    for (int i = 0; i < love[now].size(); i++)
    {
        int sj = love[now][i];//换一组物品
        DFS(sj);
        for (int v = V; v >= ali[now].v; v--)//若该节点都装不下，子结点就更不用说了，所以大于等于v
            for (int k = v - ali[now].v; k >= ali[sj].v; k--)//如果体积都小于该子结点的体积，那么就选
                //不了它及它的子结点了，所以这种情况不用枚举，付出却没有回报，划不来；
                dp[now][v] = std::max(dp[now][v], dp[now][v - k] + dp[sj][k]);
                //dp[now][v]表示给该组及之前各组v体积的情况
                int xyratlj = 1;
                show(xyratlj);
    }
}

void show(int my_thinging)
{
    //这里更新了，那么前面的最优解不会变吗？？不会的，若当前拥有的体积下，给了该组这么多的体积
    //可以比不给该组体积回报来得更大，那么前面的当前体积的分配方案就不是最优解了；
    //那如果前面的dp[now][v - k]不是最优解这个不是就要更新吗？？不用，这个是分组背包问题娅
    //这一组不就只能给出一个体积吗？（相当与只能选一个物品），所以dp[now][v - k]一定是当前
    //体积状态下，分配给该组k的体积的情况下的最优解
    //为什么要枚举那么多的v和k呢？？？dp[now][v-k]枚举到n的话相当于给前面（n-1）个物体总共分配了
    //v - k 体积时，給改组物品分配k体积时的最优解；
    //所以枚举v是为了确定后面进来的某组物品分配x体积时前面所有组分配y体积时的最优解（x+y==v）
    //而枚举k体积是因为要确定给该组多少体积时包括当前的物品的当前体积状态下的的收益最大；
    //也就是选择一个k（相当于选一个物品）；
    //为什么要逆序枚举v呢？？前面说过了，这可以看成是分组背包问题，若顺序枚举的话，后面用到的
    //dp[now][v-k]就有可能包括该组的某个物品，这显然不是分组的概念中会出现的情况；
    return;
}

int main(void)
{
    scanf("%d %d", &N, &V);
    for (int i = 1; i <= N; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if (-1 == c)root = i, ali[i] = { a,b };
        else love[c].push_back(i), ali[i] = { a,b };
    }
    DFS(root);
    printf("%d\n", dp[root][V]);
    return 0;
}