Динамическое программирование Change Maker

Question

Я пытаюсь преобразовать следующий алгоритм, и я получил его в основном работающим, однако есть пример из книги, которую я использую, которая говорит, что я ввожу номиналы 1,3,4 и значение 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, и он работает, но он не возвращает вывод 2 а точнее ноль.

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

Оператор возврата находится не в том месте. Это должно быть за пределами 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