Lua：単価が異なるお菓子をどういう組み合わせで買えば目標の合計値になるか問題

okashi.lua

function okashi(total, prices)
  local count, solved = solve(total, prices)
  print_solution(count, solved, total, prices)
end

function print_solution(count, solved, total, prices)
  if solved then
    for i = 1, #prices do
      io.stdout:write(("%d円のが%d個"):format(prices[i], count[i]))
      if i ~= #prices then io.stdout:write("、") end
    end
    io.stdout:write(("で%d円になる。\n"):format(total))
  else
    io.stdout:write("解が見つかりません。\n")
  end
end

function solve(total, prices)
  local count = {}
  for i = 1, #prices do
    total = total - prices[i]
    count[i] = 1
  end
  if total < 0 then
    return nil, false
  else
    return solve_aux(total, prices, count)
  end
end

function solve_aux(total, prices, count)
  local array = {}
  for i = 1, total do array[i] = 0 end
  for i = 1, #prices do
    one_item(array, total, prices, i)
  end
  if array[total] == 0 then
    return nil, false
  else
    pick_item(array, total, prices, count)
    return count, true
  end
end

function one_item(array, total, prices, idx)
  local price = prices[idx]
  for i = price, total do
    if array[i] == 0 and
       (i == price or array[i - price] > 0) then
       array[i] = idx
    end
  end
end

function pick_item(array, total, prices, count)
  while total > 0 do
    local idx = array[total]
    total = total - prices[idx]
    count[idx] = count[idx] + 1
  end
end

okashi(3000, {146,172,400,500})
okashi(9731, {146,172,400,500})
okashi(129414, {146,172,400,500})

expl3版をそのままの構成でLuaに移植したもの。
（だからLuaのプログラムとしては不自然な点がある）