通过 DAG 寻找总路径成本等于或尽可能接近某个值的路径
Finding path through DAG with a total path cost equal or as close as possible to some value
我正在解决一个问题，该问题已概括为我在标题中描述的内容。本质上，我有一个看起来像这样的 DAG：（我知道 DAG 看起来像什么并不重要，我只是认为它可能会显示我所在的位置）。
我将顶点值绘制为层中顶点的边缘距离（或成本），其中层由垂直对齐的顶点组成。换句话说，当 a 和 b 在同一“层”中时，边 (a,a') (b,a') 具有相等的值。
我需要找到从最左边的层到最右边的层的路径，使得路径中边的值之和等于或小于并尽可能接近目标值。
最初的问题基本上是找到不同矩阵中等于（或小于并尽可能接近）目标值的单个值的总和，其中每个值恰好使用一个值。
我必须使用制表，但我不确定如何解决这个问题。我不是在寻找完整的解决方案。如果这个问题写得不好请告诉我。
- 从每一层取最小成本节点得到最小成本路径
- 从每一层取最大成本节点得到最大成本路径
- 如果目标超出最小值和最大值之间的范围，则完成
- 使最小路径成为当前路径
- select 与同一层路径中的节点具有最大正增量但在与当前路径中的节点交换时不会将路径成本置于目标之上的节点。交换。
- 重复最后一步，直到不能再交换为止。
首先，我会评论说 'Given n sets of integers and bound B, select one number from each set to achieve the largest sum <= B' 的原始问题表述比 DAG 路径类比要简单得多，所以我会坚持这一点。
不幸的是，问题是 NP-Hard 通过从子集总和减少：给定子集总和与宇宙 S = (s1, s2, ... sn) 和目标 B 的实例，创建一个 n 组大小为 2 的问题实例：(s1, 0), (s2, 0), ... (sn, 0)。边界 B 是可达的当且仅当存在一个子集总和等于 B.
幸运的是，如果你的值都很小，你可以使用类似于子集求和算法的伪多项式算法：
- 初始化一个长度为 (B+1) 的布尔数组 A，除 A[0] = True 外所有值为 false
- 对于集合列表中的每个集合 S：
初始化一个新的布尔数组 A'，长度为 (B+1)，所有值为 False。
对于 S 中的每个数字 x:
- 对于每个 A[i] = True 的索引 i：如果在范围内，则设置 A'[i+x] = True。
交换 A 和 A'。
我正在解决一个问题，该问题已概括为我在标题中描述的内容。本质上，我有一个看起来像这样的 DAG：（我知道 DAG 看起来像什么并不重要，我只是认为它可能会显示我所在的位置）。
我需要找到从最左边的层到最右边的层的路径，使得路径中边的值之和等于或小于并尽可能接近目标值。
最初的问题基本上是找到不同矩阵中等于（或小于并尽可能接近）目标值的单个值的总和，其中每个值恰好使用一个值。
我必须使用制表，但我不确定如何解决这个问题。我不是在寻找完整的解决方案。如果这个问题写得不好请告诉我。
- 从每一层取最小成本节点得到最小成本路径
- 从每一层取最大成本节点得到最大成本路径
- 如果目标超出最小值和最大值之间的范围，则完成
- 使最小路径成为当前路径
- select 与同一层路径中的节点具有最大正增量但在与当前路径中的节点交换时不会将路径成本置于目标之上的节点。交换。
- 重复最后一步，直到不能再交换为止。
首先，我会评论说 'Given n sets of integers and bound B, select one number from each set to achieve the largest sum <= B' 的原始问题表述比 DAG 路径类比要简单得多，所以我会坚持这一点。
不幸的是，问题是 NP-Hard 通过从子集总和减少：给定子集总和与宇宙 S = (s1, s2, ... sn) 和目标 B 的实例，创建一个 n 组大小为 2 的问题实例：(s1, 0), (s2, 0), ... (sn, 0)。边界 B 是可达的当且仅当存在一个子集总和等于 B.
幸运的是，如果你的值都很小，你可以使用类似于子集求和算法的伪多项式算法：
- 初始化一个长度为 (B+1) 的布尔数组 A，除 A[0] = True 外所有值为 false
- 对于集合列表中的每个集合 S：
初始化一个新的布尔数组 A'，长度为 (B+1)，所有值为 False。
对于 S 中的每个数字 x:
- 对于每个 A[i] = True 的索引 i：如果在范围内，则设置 A'[i+x] = True。
交换 A 和 A'。