以我自己的经验(还会继续更新 只要我还能继续遇到这类题目 )
树形背包一般分两种:
- $$ f[u][j]表示以u为根节点的子树花费j所得到的最优策略(当然这个时间复杂度比较高 O(NM^2)) $$
- $$ f[u][j]表示以u为根节点的子树选j个子节点所得到的最优策略(时间复杂度一般为O(NM)) $$
选课
这题的每一个物品的体积都是1,所以代码比较容(kun)易(nan)写
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 3030;
int n, m;
int s[N];
int f[N][N];
int e[N], ne[N], h[N], idx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int dfs(int u)
{
int res = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int z = e[i];
int t = dfs(z);
res += t;
for (int j = res - 1; j; j --)
for (int k = 1; k <= t; k ++)
if (j >= k) f[u][j] = max(f[u][j], f[u][j - k] + f[z][k]);
}
for (int i = res; i; i --)
f[u][i] = f[u][i - 1] + s[u];
return res;
}
int main()
{
scanf ("%d %d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++)
{
int p;
scanf ("%d %d", &p, &s[i]);
add(p, i);
}
dfs(0);
printf ("%d", f[0][m + 1]);
return 0;
}
有依赖的背包问题
在考虑每个儿子节点时,考虑留给儿子的体积和留给父亲的体积的所有决策中的最大值
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N];
int e[N], ne[N], h[N], idx;
int f[N][N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u)
{
for (int i = h[u]; ~i; i = ne[i])
{
int son = e[i];
dfs(son);
for (int j = m - v[u]; j >= 0; j --) // 要给节点u留出空间
for (int k = 0; k <= j; k ++) // 循环决策(分给子树多少体积)
f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
}
// 把节点u也考虑上
for (int j = m; j >= v[u]; j --) f[u][j] = f[u][j - v[u]] + w[u];
// 要把不能装下节点u的方案的价值都归0(父节点都装不下了,那子树上的所有节点也不需要考虑了)
for (int j = 0; j < v[u]; j ++) f[u][j] = 0;
}
int main()
{
scanf ("%d %d", &n, &m);
int root;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++)
{
int p;
scanf ("%d %d %d", &v[i], &w[i], &p);
if (p == -1) root = i;
else add(p, i);
}
dfs(root);
printf ("%d", f[root][m]);
return 0;
}
有线电视网
这题便是用第二种策略的思想(我感觉还是挺难想的)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 3030;
int n, m;
int v[N];
int e[N], h[N], ne[N], w[N], idx;
int f[N][N]; // f[i][j]表示以i为根节点的子树中选j个用户所获得的最大利润
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int dfs(int u) // 返回以u为根的子树所包含的用户的个数
{
if (u > n - m) // 如果它是用户的话
{
f[u][1] = v[u];
return 1; // 直接返回1就可以了
}
int sum = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int z = e[i];
int t = dfs(z);
sum += t; // 以u为根节点的子树所包含的用户的个数
// 做一次分组背包就可以了
for (int j = sum; j; j --)
for (int k = 1; k <= t; k ++)
if (j >= k)
f[u][j] = max(f[u][j], f[u][j - k] + f[z][k] - w[i]);
}
return sum;
}
int main()
{
scanf ("%d %d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 1; i <= n - m; i ++)
{
int K;
scanf ("%d", &K);
while (K --)
{
int a, b;
scanf ("%d %d", &a, &b);
add(i, a, b);
}
}
memset(f, ~0x3f, sizeof f);
for (int i = 1; i <= n; i ++) f[i][0] = 0;
for (int i = n - m + 1; i <= n; i ++) scanf ("%d", &v[i]);
dfs(1);
int res;
for (res = m; res; res --) // 从选用户最多的开始找,如果找到利润大于0便是答案
if (f[1][res] >= 0) break;
printf ("%d", res);
return 0;
}