通过棋盘找到最接近给定成本的路径
Finding a path through a checkerboard which is closest to a given cost
我一直被一个问题困住了。我现在正在上算法课程，但这不是作业问题。我们还没有在 class 中进行动态编程，我只是自己做。
Given a NxN sized checkerboard where every coordinate has a cost and another integer M, find the cost of a path from the top left of the checkerboard to the bottom right of the checkerboard (only allowed moves are right or down 1 square) such that the total cost of the path is below M but as close to M as possible. All elements of NxN and M are positive.
如果这要求我找到最小或最大路径，我可以使用标准的动态规划算法，但由于我受 M 的限制，我想我必须使用另一种策略。我一直在尝试使用记忆并构建一个数组，其中填充了一组从开始到给定元素的所有可能路径的成本。为了构造 (i, j) 的集合，我将 (i, j) 的成本值添加到 (i-1, j) 和 (j-1, i) 的集合并集中的每个元素（如果它们存在，否则只需使用集合 {0} 代替它）。一旦我为棋盘中的所有元素完成此操作，选择正确的路径就很简单了。只需在 (N, N) 的集合中选择低于 M 但最接近 M 的元素。
例如：
+---+---+---+
| 0 | 1 | 3 |
| 3 | 2 | 1 |
| 5 | 2 | 1 |
+---+---+---+
到给定点的路径成本：
+---+----------+----------------+
| 0 | 1 | 4 |
| 3 | 3, 5 | 4, 5, 6 |
| 8 | 5, 7, 10 | 5, 6, 7, 8, 11 |
+---+----------+----------------+
这确实是一种 space 低效的做事方式。如果我算对了，(N, N) 节点集合中元素数量的最坏情况是 (N+1)!/((N+1)/2)!。有没有更快（space 或时间）的方法来解决我缺少的这个问题？
没有。如果所有成本都是整数，则在每个单元格中您最多需要存储 O(M) 个元素。所以你需要 O(MN^2) 内存。如果总和>M，你就忽略它。
在此 paper 中提到了解决类似问题（精确成本）的伪多项式算法。您可以多次使用相同的算法，精确成本 = M..1，或者阅读算法并找到直接解决您问题的变体。
不幸的是，这篇论文是付费的:(
我一直被一个问题困住了。我现在正在上算法课程，但这不是作业问题。我们还没有在 class 中进行动态编程，我只是自己做。
Given a NxN sized checkerboard where every coordinate has a cost and another integer M, find the cost of a path from the top left of the checkerboard to the bottom right of the checkerboard (only allowed moves are right or down 1 square) such that the total cost of the path is below M but as close to M as possible. All elements of NxN and M are positive.
如果这要求我找到最小或最大路径，我可以使用标准的动态规划算法，但由于我受 M 的限制，我想我必须使用另一种策略。我一直在尝试使用记忆并构建一个数组，其中填充了一组从开始到给定元素的所有可能路径的成本。为了构造 (i, j) 的集合，我将 (i, j) 的成本值添加到 (i-1, j) 和 (j-1, i) 的集合并集中的每个元素（如果它们存在，否则只需使用集合 {0} 代替它）。一旦我为棋盘中的所有元素完成此操作，选择正确的路径就很简单了。只需在 (N, N) 的集合中选择低于 M 但最接近 M 的元素。
例如：
+---+---+---+
| 0 | 1 | 3 |
| 3 | 2 | 1 |
| 5 | 2 | 1 |
+---+---+---+
到给定点的路径成本：
+---+----------+----------------+
| 0 | 1 | 4 |
| 3 | 3, 5 | 4, 5, 6 |
| 8 | 5, 7, 10 | 5, 6, 7, 8, 11 |
+---+----------+----------------+
这确实是一种 space 低效的做事方式。如果我算对了，(N, N) 节点集合中元素数量的最坏情况是 (N+1)!/((N+1)/2)!。有没有更快（space 或时间）的方法来解决我缺少的这个问题？
没有。如果所有成本都是整数，则在每个单元格中您最多需要存储 O(M) 个元素。所以你需要 O(MN^2) 内存。如果总和>M，你就忽略它。
在此 paper 中提到了解决类似问题（精确成本）的伪多项式算法。您可以多次使用相同的算法，精确成本 = M..1，或者阅读算法并找到直接解决您问题的变体。
不幸的是，这篇论文是付费的:(