A Knapsack Problem

---

title: A Knapsack Problem
date: 2018-11-08 00:07:00
tags:
- Algorithm
mathjax: true

---

题意

(n(1 leq n leq 1000))个结点的树，每个结点有重量(w)和价值(v)两个属性，现在给你一个大小为(m(1 leq m leq 1000))的背包，求能得到的最大价值。注：选取的结点一定是一个连通块。

题解

记最终选取的集合为(S)，当前枚举的点为(u)，编号为(i)的点是(x[i]​)，有两种情况：

• (u in S)
• (u otin S)

对于第二种情况，把原来的问题划分成了具有相同性质的几个子问题((dp)的性质)。重点来啦，如果当前点不选，那么下一次枚举应该选择哪个点，能使递推的次数最少？如果选择树的重心，显然是最优的，既删除选择的这个点后，其剩下的最大子树的(Size)最小。根据这样的策略，递推的深度就能控制在(log(n))范围内。

对于第一种情况，求一遍树的(DFS)序，不考虑树的结构，直接递推即可。(dp[i][j]:=)结点编号序列为([1,i ])，负重为(j)得到的最大价值.

• 选择编号为(i)的结点加入背包，(dp[i][j] = max(dp[i][j], dp[i - 1][j - Size(x[i])] + value(x[i]))).
• 不选择编号为(i)的点加入背包，(dp[i + subree[x[i]] - 1][j] = max(dp[i + subree[x[i]] - 1][j], dp[i - 1][j]))

复杂度(O(nmlog(n)))

代码

using namespace std;

const int N = 2005;

int n, m;
int s[N], v[N], subtree[N], label[N], dp[N][N];
bool deleted[N];

vector<int> adj[N];

void DFS(int u, int par = -1) {
    subtree[u] = 1;
    for (auto v : adj[u]) if ((!deleted[v]) && (v != par)) {
        DFS(v, u);
        subtree[u] += subtree[v];
    }
    label[n] = u; n--;
}

int central(int u, int par = -1) {
    int w = 0;
    for (auto v : adj[u]) if ((!deleted[v]) && (v != par)) {
        if (subtree[v] > subtree[w]) w = v;
    }
    if (w == 0) return (u);
    if (subtree[w] + subtree[w] <= n) return (u);
    return (central(w, u));
}

int calc(int n) {
    Rep(i, 0, n) Rep(j, 0, m) dp[i][j] = -INF32;

    dp[1][s[label[1]]] = v[label[1]];

    Rep(i, 2, n) {
        int u = label[i];
        Rep(j, 0, m) {
            if (j >= s[u]) dp[i][j] = max(dp[i][j], dp[i - 1][j - s[u]] + v[u]);
            dp[i + subtree[u] - 1][j] = max(dp[i + subtree[u] - 1][j], dp[i - 1][j]);
        }
    }

    int res = 0;
    Rep(i, 0, m) res = max(res, dp[n][i]);
    return res;
}

int solve(int tree, int tree_size) {
    n = tree_size; DFS(tree);
    n = tree_size;

    int r = central(tree);
    n = tree_size; DFS(r);

    int res = calc(tree_size);
    deleted[r] = true;

    for (auto v : adj[r]) if (!deleted[v]) res = max(res, solve(v, subtree[v]));
    return res;
}

int main()
{
    BEGIN() {
        sc(n), sc(m);
        Rep(i, 0, n) deleted[i] = false;
        Rep(i, 0, n) adj[i].clear();

        Rep(i, 1, n) sc(s[i]);
        Rep(i, 1, n) sc(v[i]);
        rep(i, 1, n) {
            int u, v;
            sc(u), sc(v);
            adj[u].pb(v);
            adj[v].pb(u);
        }
        int result = solve(1, n);
        pr(result);
    }
    return 0;
}