动态规划找零钱

我试图转换下面的算法,并且我大部分都已经完成了,但是书上有一个例子说我输入1、3、4的面额和6的值时,将获得2的输出。

--[[
ALGORITHM ChangeMaking(D[1..m], n)
//应用动态规划来找到最小数量的硬币
//面额为d1<d2<...<dm,其中d1=1,相加为给定数量n
//输入:正整数n和递增正整数组成的数组D[1..m]表示硬币面值,其中D[1]=1
//输出:相加为n的最小硬币数
F[0]←0
for i ←1 to n do
temp←∞; j ←1
while j ≤ m and i ≥ D[j ] do
temp ←min(F [i − D[j ]], temp)
j ←j + 1
F[i]←temp + 1
return F[n]
]]

以下是我尝试转换代码并使其正常工作的方式。 我遇到了一些问题,当尝试设置temp = math.if时,我会收到错误消息说预期数字,但接收到了nil,所以我将其换成了math.huge,虽然它可以正常工作,但却没有返回2的输出而是nil。

function ChangeMaking(D,n)
--[[
//应用动态规划来找到最小数量的硬币
//面额为d1<d2<...<dm,其中d1=1,相加为给定数量n
//输入:正整数n和递增正整数组成的数组D[1..m]表示硬币面值,其中D[1]=1
//输出:相加为n的最小硬币数
]]
F = {}
m = tablelength(D)
F[0] = 0
  for i =1,n do
    temp = math.inf
    j = 1
    while j <= m and i >= D[j] do
      temp = math.min(F[ i - D[j] ], temp)
      j = j + 1
    end
    F[i] = temp + 1
  return F[n]
  end
end
function main()
  print("你好,欢迎使用找零钱- LUA版")
  print("输入一系列硬币面值,以空格分隔")
  input = io.read()
  deno = {}
   for num in input:gmatch("%d+") do table.insert(deno,tonumber(num)) end
  local i = 1
  while i ~= 0 do
    print("请键入找零钱的总数")
    input2 = io.read("*n")
    if input2 == 0 then i=0 end
    print(ChangeMaking(deno,input2))
  end
end
function tablelength(T)
--[[
//用于获取表的总长度的函数。
]]
  local count = 0
  for _ in pairs(T) do count = count + 1 end
  return count
end
main()
--[[
    输出
    你好,欢迎使用找零钱- LUA版
    输入一系列硬币面值,以空格分隔
    1 3 4
    请键入找零钱的总数
    6
    nil
]]
点赞
用户9383219
用户9383219

返回语句放错位置了。它需要放在 for 循环的外面。在你的版本中,for 循环只迭代一次,然后函数返回 F[1],它是 nil

function ChangeMaking(D, n)
    F = {}
    m = tablelength(D)
    F[0] = 0
    for i = 1, n do
        temp = math.huge
        j = 1
        while j <= m and i >= D[j] do
            temp = math.min(F[ i - D[j] ], temp)
            j = j + 1
        end
        F[i] = temp + 1
    end
    return F[n]
end
2018-03-14 02:10:25