best_vertex = None
max = 0
for v in graph.vertices:
n = largest_area(graph, cost, v)
if n > max:
best_vertex = v
max = n
def largest_area(graph, max_cost, vertex, edges=[]):
# Base Case
if max_cost <= 0:
return edges
# Iterate through all the neighbours and find the highest scoring path.
max_vertices = 0
for n in graph.adjacent(vertex):
edge = graph.get_edge(n, vertex)
if edge in edges: continue # We've already taken that route.
num_vertices = largest_area(graph, max_cost - edge.weight, edges + [edge])
if num_vertices > max_vertices:
max_vertices = num_vertices
return max_vertices
1 回答
这听起来像the Knapsack problem的修改版本 .