l********1
发帖数: 990 | 1 有一个graph，每个node有自己的weight。如何找出subgraph， 让subgroup所有node的
weight和为k.
这道题属于什么难度呢？
菜鸟对graph很头痛，求大家指教。 |
t***t
发帖数: 6066 | 2 anything to do with graph?
this question is same as give n numbers, find subset whose sum is k |
z***m
发帖数: 1602 | 3 subset sum里面元素可以任意取，但是这个问题，必须有path相互连接的才能取。比如
2->3->5, 让你凑7， 就没办法了。
【在 t***t 的大作中提到】
: anything to do with graph?
: this question is same as give n numbers, find subset whose sum is k
|
l********1
发帖数: 990 | 4 Yes.
any solution for the question? how to most effectively find all the
subgraphs if any.
【在 z***m 的大作中提到】
: subset sum里面元素可以任意取，但是这个问题，必须有path相互连接的才能取。比如
: 2->3->5, 让你凑7， 就没办法了。
|
l********1
发帖数: 990 | |
r****7
发帖数: 2282 | 6 用动态规划，你还要在node里加上一个元素，是你处理的subgraph的weight之和
不过这个题是比较难的，我觉得面试中不会遇到
【在 l********1 的大作中提到】
: 有一个graph，每个node有自己的weight。如何找出subgraph， 让subgroup所有node的
: weight和为k.
: 这道题属于什么难度呢？
: 菜鸟对graph很头痛，求大家指教。
|
w**********o
发帖数: 140 | 7 給個這個思路: 用DFS找sub-graph, 然後用backtracking來做. |
