动态规划找零钱
2018-3-13 2:32:56
收藏:0
阅读:83
评论:1
我试图转换下面的算法,并且我大部分都已经完成了,但是书上有一个例子说我输入1、3、4的面额和6的值时,将获得2的输出。
--[[
ALGORITHM ChangeMaking(D[1..m], n)
//应用动态规划来找到最小数量的硬币
//面额为d1<d2<...<dm,其中d1=1,相加为给定数量n
//输入:正整数n和递增正整数组成的数组D[1..m]表示硬币面值,其中D[1]=1
//输出:相加为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时,我会收到错误消息说预期数字,但接收到了nil,所以我将其换成了math.huge,虽然它可以正常工作,但却没有返回2的输出而是nil。
function ChangeMaking(D,n)
--[[
//应用动态规划来找到最小数量的硬币
//面额为d1<d2<...<dm,其中d1=1,相加为给定数量n
//输入:正整数n和递增正整数组成的数组D[1..m]表示硬币面值,其中D[1]=1
//输出:相加为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("你好,欢迎使用找零钱- LUA版")
print("输入一系列硬币面值,以空格分隔")
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("请键入找零钱的总数")
input2 = io.read("*n")
if input2 == 0 then i=0 end
print(ChangeMaking(deno,input2))
end
end
function tablelength(T)
--[[
//用于获取表的总长度的函数。
]]
local count = 0
for _ in pairs(T) do count = count + 1 end
return count
end
main()
--[[
输出
你好,欢迎使用找零钱- LUA版
输入一系列硬币面值,以空格分隔
1 3 4
请键入找零钱的总数
6
nil
]]
点赞
评论区的留言会收到邮件通知哦~
推荐文章
- Lua 虚拟机加密load(string.dump(function)) 后执行失败问题如何解决
- 我想创建一个 Nginx 规则,禁止访问
- 如何将两个不同的lua文件合成一个 东西有点长 大佬请耐心看完 我是小白研究几天了都没搞定
- 如何在roblox studio中1:1导入真实世界的地形?
- 求解,lua_resume的第二次调用继续执行协程问题。
- 【上海普陀区】内向猫网络招募【Skynet游戏框架Lua后端程序员】
- SF爱好求教:如何用lua实现游戏内调用数据库函数实现账号密码注册?
- Lua实现网站后台开发
- LUA错误显式返回,社区常见的规约是怎么样的
- lua5.3下载库失败
- 请问如何实现文本框内容和某个网页搜索框内容连接,并把网页输出来的结果反馈到另外一个文本框上
- lua lanes多线程使用
- 一个kv数据库
- openresty 有没有比较轻量的 docker 镜像
- 想问一下,有大佬用过luacurl吗
- 在Lua执行过程中使用Load函数出现问题
- 为什么 neovim 里没有显示一些特殊字符?
- Lua比较两个表的值(不考虑键的顺序)
- 有个lua简单的项目,外包,有意者加微信 liuheng600456详谈,最好在成都
- 如何在 Visual Studio 2022 中运行 Lua 代码?

返回语句放错位置了。它需要放在
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