最近遇到一个问题。我必须找到从多维整数数组的左上角到右下角的路径的成本。此路径的成本必须是不超过某个提供值的最大成本。
路径的成本定义为该路径经过的数组索引值的总和。每条路径的起点总是左上角,每条路径的终点总是右下角。此外,您只能向右或向底部移动。
假设这是我要用于此问题的多维数组,提供的值为 12。
+---+---+---+
| 0 | 2 | 5 |
+---+---+---+
| 1 | 1 | 3 |
+---+---+---+
| 2 | 1 | 1 |
+---+---+---+
这是我应该找到的正确路径。此路径的成本为 11,它是低于或等于给定值的所有路径的最高成本。
+---+---+---+
| X | X | X |
+---+---+---+
| 1 | 1 | X |
+---+---+---+
| 2 | 1 | X |
+---+---+---+
我试图用 Python 解决这个问题,但我看不出哪里出错了。下面是我的一段代码。
def answer (food, grid):
# Grid is N*N in size
n = len(grid)
# Memoize a given function
def memoize (f):
memo = {}
def helper (r, c, k):
i = c + (r * n)
if i not in memo:
memo[i] = f(r, c, k)
return memo[i]
return helper
# Get cost function
def get_cost (r, c, k):
if r >= n or c >= n:
return -1
if k < grid[r][c]:
return -1
if r == n - 1 and c == n - 1:
return grid[r][c]
down = get_cost(r + 1, c, k - grid[r][c])
right = get_cost(r, c + 1, k - grid[r][c])
if down < 0 and right < 0:
return -1
return grid[r][c] + max(down, right)
# Memoize the get cost function
get_cost = memoize(get_cost)
return get_cost(0, 0, food)
print answer (12, [[0, 2, 5], [1, 1, 3], [2, 1, 1]])
我总是得到 16 的答案,而我应该得到 11 的答案。有人可以帮我解决这个问题吗?
编辑:
我更改了我的 memoize 代码以在索引中包含给定的食物值。我得到了正确的答案。但是,仍有其他情况不起作用。 (在这些情况下我没有得到输入,所以我看不出哪里出了问题)。
这是我更新后的代码。
# Memoize a given function
def memoize (f):
memo = {}
def helper (r, c, k):
i = (k * food) + (c + (r * n))
if i not in memo:
memo[i] = f(r, c, k)
return memo[i]
return helper
最佳答案
您可以将您的内存功能更新为如下内容:
def memoize (f):
memo = {}
def helper(*args):
if args not in memo:
memo[args] = f(*args)
return memo[args]
return helper
grid = [[0,2,5],[1,1,3],[2,1,1]]
answer(12, grid)
# 11
只要您的参数是可哈希的,您就可以使用 *args
作为函数的参数,并将 args
作为内存缓存的键。这与使用参数的元组作为键相同。
def fn(*args):
print(args)
fn(1,2,3)
(1, 2, 3)
由 i = c + (r * n)
组成的原始内存缓存键排除了考虑 k
并且还允许不同 c 和r 组合。
关于python - 寻找最接近给定值的路径旅行成本,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31097402/