有依赖的背包问题
算法分析
- dp数组的含义:
dp[u][v]
表示以u为根节点,背包体积为v时所获得的最大价值 - 根据依赖关系,所以每次都必须把u选上,再考虑子树,结合分组背包的思想,将每种剩余的体积看成一组。然后看剩余体积分给各个子树,各个子树利用这些剩余体积能拼凑出的最大价值是多少。
Python 代码
n,V = map(int,input().split())
edge = [[] for i in range(n+1)]
v = [0]
w = [0]
dp = [[0 for i in range(V+1)]for i in range(n+1)]
for i in range(1, n + 1): #建立树形关系
v1,w1,p = map(int,input().split())
if p == -1:
root = i
v.append(v1)
w.append(w1)
else:
v.append(v1)
w.append(w1)
edge[p].append(i)
def dfs(u):
for i in range(v[u], V+1): #初始化,u结点必选
dp[u][i] += w[u]
for son in edge[u]:
dfs(son)
for j in range(V, v[u]-1, -1): #遍历V ~ v[u] 因为必须要装的下父节点
for k in range(j - v[u] + 1): #根据剩余体积分组
dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k])
dfs(root)
print(dp[root][V])
C++
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int n, V, root;
int idx = 1, e[N], ne[N], head[N], w[N], v[N];
int dp[N][N];
void add(int u, int v)
{
e[idx] = v; ne[idx] = head[u]; head[u] = idx ++;
}
void dfs(int u)
{
for (int i = v[u]; i <= V; i ++) dp[u][i] += w[u];
for (int i = head[u]; i; i = ne[i])
{
int son = e[i];
dfs(son);
for (int j = V; j >= v[u]; j --)
for (int k = 0; k <= j - v[u]; k ++)
dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k]);
}
}
int main()
{
cin >> n >> V;
for (int i = 1; i <= n; i ++)
{
int v1, w1, p;
cin >> v[i] >> w[i] >> p;
if (p == -1) root = i;
else add(p, i);
}
dfs(root);
cout << dp[root][V] << endl;
return 0;
}