Skip to content

Instantly share code, notes, and snippets.

@zr-tex8r

zr-tex8r/okashi.lua

Created Jan 26, 2020
Embed
What would you like to do?
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

This comment has been minimized.

Copy link
Owner Author

@zr-tex8r zr-tex8r commented Jan 26, 2020

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment