网格难题中最昂贵的可能路径算法

Question

目标

从正方形网格的左上角到右下角寻找最昂贵的路径，使其总成本低于给定的阈值。

场景

1. 您将得到一个正方形NxN网格。
2. 你要付出最大的代价。
3. 网格中的每个单元都有代价。左上角的单元格花费了0。
4. 路径的成本是路径中单元格成本的总和。它的“成本盈余”是从最大成本中减去成本的结果。
5. 运动总是对一个细胞或向下一个细胞。
6. 起点是网格的左上角单元格，目标是右下角单元格。
7. 您必须输出任何具有非负成本盈余的路径的最小成本盈余，或者-1如果没有这样的路径(最大成本是不够的)。

输入限制

1. N将介于1到20之间。
2. 最高费用将在1至200之间包括在内。
3. 每个单元格的费用将在0至10 (含)之间。

示例

1. 最大成本:9 网格: 0 1 5 2 3 2 2 3 2 2 2预期输出:0 解释:有一条成本为9和成本盈余为0的路径0 2 2 3 2。
2. 最大成本: 15 网格:0 1 5 2 3 2 2 32 2预期输出:5 解释:最昂贵的路径是成本10和成本盈余5的0 1 5 2 2。
3. 最大成本: 6 网格:0 1 5 2 2 3 2 2 32 2预期输出：-1 解释:最便宜的路径是成本8的0 1 3 2 2，大于6。

Answer 1

VBScript 191

这假设数组位于一个名为A的变量中，成本在一个名为c的变量中。

Dim M
Sub f(s,i,j,v)
If i>s And j=s And v<=c And M<v Then M=v
If i>s Or j>s Then Exit Sub
f s,i+1,j,v+A(i)(j)
f s,i,j+1,v+A(i)(j)
End Sub
f UBound(A),0,0,0
If M=0Then MsgBox-1 Else MsgBox c-M

要运行它，将以下行放在名为x.vbs的文件的顶部，然后粘贴到上面的代码中，只需双击或执行cscript x.vbs

A=Array(Array(0,1,5),Array(2,3,2),Array(2,3,2))
c=6