{{ message }}

Instantly share code, notes, and snippets.

# zr-tex8r/okashi.lua

Created Jan 26, 2020
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})

### zr-tex8r commented Jan 26, 2020

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