来源于yxc视频讲解,python3代码实现
python3 代码
N=110
h,e,ne,idx=[-1 for _ in range(N)],[0 for _ in range(N)],[0 for _ in range(N)],0
v,w = [0 for _ in range(N)],[0 for _ in range(N)]
dp = [[0 for _ in range(N)] for _ in range(N)]
def add(a,b):
global idx
e[idx]=b
ne[idx]=h[a]
h[a]=idx
idx+=1
def dfs(u):
i = h[u]
while i!=-1:
son =e[i]
dfs(son)
for j in range(V-v[u],-1,-1):
for k in range(j+1):
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[son][k])
i=ne[i]
for i in range(V,v[u]-1,-1):
dp[u][i] = dp[u][i-v[u]]+w[u]
for i in range(v[u]):
dp[u][i]=0
if __name__ == '__main__':
N, V = input().strip().split()
N, V = int(N), int(V)
root=0
for i in range(1,N+1):
v[i],w[i],p = input().strip().split()
v[i], w[i], p = int(v[i]),int(w[i]),int(p)
if p==-1:
root =i
else:
add(p,i)
dfs(root)
print(dp[root][V])
存储方式 是 链式前向星
我也就将C++代码改写成python3,代码里设计的h,e,ne我还没搞懂