动态规划创客

Question

我正在尝试转换以下算法，并且我已经使它大部分工作，但是我正在使用的书中有一个示例说我输入了 1、3、4 的面额和 n 值6 并接收 2.

的输出

--[[
ALGORITHM ChangeMaking(D[1..m], n)
//Applies dynamic programming to find the minimum number of coins
//of denominations d1< d2 < . . . < dm where d1 = 1 that add up to a
//given amount n
//Input: Positive integer n and array D[1..m] of increasing positive
// integers indicating the coin denominations where D[1]= 1
//Output: The minimum number of coins that add up to 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 时，我收到一条错误消息，说预期的数字，但收到的是零，所以我将它换成 math.huge 并且它有效但是它不是 return 输出 2，而是 nil。

function ChangeMaking(D,n)
--[[
//Applies dynamic programming to find the minimum number of coins
//of denominations d1< d2 < . . . < dm where d1 = 1 that add up to a
//given amount n
//Input: Positive integer n and array D[1..m] of increasing positive
// integers indicating the coin denominations where D[1]= 1
//Output: The minimum number of coins that add up to 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("Hello Welcome the to Change Maker - LUA Edition")
  print("Enter a series of change denominations, separated by spaces")
  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("Please Enter Total for Change Maker")
    input2 = io.read("*n")
    if input2 == 0 then i=0 end
    print(ChangeMaking(deno,input2))
  end
end
function tablelength(T)
--[[
//Function for grabbing the total length of a table.
]]
  local count = 0
  for _ in pairs(T) do count = count + 1 end
  return count
end
main()
--[[
    OUTPUT
    Hello Welcome the to Change Maker - LUA Edition
    Enter a series of change denominations, separated by spaces
    1 3 4
    Please Enter Total for Change Maker
    6
    nil
]]

Answer 1

return 语句在错误的地方。它需要在 for 循环之外。在您的版本中，for 循环迭代一次，然后是函数 returns 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

动态规划创客

Dynamic Programming Change Maker

lua

dynamic-programming

coin-change