使用memoization的BestSum函数的Lua实现

Question

我正在尝试翻译下面的javascript "bestSum"lua中的记忆函数:

const bestSum = (targetSum,numbers,memo ={}) => {
if(targetSum in memo) return memo[targetSum];
if(targetSum === 0 ) return [];
if(targetSum <0)return null;
let shortestCombination = null;
for (let num of numbers) {
const remainder = targetSum - num;
const remainderCombination = bestSum(remainder,numbers,memo);
if (remainderCombination !==null) {
const combination = [...remainderCombination, num];
if (shortestCombination === null || combination.length < shortestCombination.length) 
{
shortestCombination = combination;
}
}
}
memo [targetSum] = shortestCombination;
return shortestCombination;
}

带有正确结果的示例测试用例:

console.log(bestSum(7,[5,3,4,7])); //[7]
console.log(bestSum(8,[2,3,5])); //[3,5]
console.log(bestSum(8,[1,4,5])); //[4,4]
console.log(bestSum(100,[1,2,5,25])); //[25,25,25,25] 

我将上面的javascript翻译成lua如下:

local function BestSum(target_sum,numbers,memo)
if memo[target_sum] ~= nil then return  memo[target_sum] end
if target_sum == 0 then  return {} end
if target_sum < 0 then return nil end

local shortest_combination = nil

for i, num in ipairs (numbers) do
local remainder = target_sum - num
local remainder_combination =  BestSum(remainder,numbers, memo) 
if remainder_combination ~= nil then
local combination = remainder_combination
table.insert(combination,num )
if (shortest_combination == nil) or (#combination < #shortest_combination )then          
shortest_combination = combination
end
end
end
memo[target_sum] = shortest_combination;
return shortest_combination;
end 

但最后两种情况没有得到期望的结果......而得到错误的结果:

BestSum(8,{1,4,5},{})==>{"4","1","4"}
BestSum(150,{5,25},{})==>  

{"25","5","5","5","5","5","25","5","25","5","25","5","25","5","25","5","25","5","25","5","25","5","25","5","25","5","25","5","25","5","25","5","25","5","; 25","5","25","5","25","5","25","5","25","5","25","5","25"}

结果甚至都不正确，更不用说"最好"了。情况? ?

有谁能指出我错在哪里吗?

感谢

Answer 1

问题是翻译的这一部分:

local combination = remainder_combination
table.insert(combination, num)

表是通过引用传递的，所以这不是创建一个新表，它只是将变量combination赋值给同一个表。修改combination，就是给remainder_combination增加数据。

JavaScript版本正在注意创建一个新的数组，并填充它与remainderCombination数组的内容(使用'…'，展开操作符):

const combination = [...remainderCombination, num];

这是最准确的Lua翻译:

local combination = {unpack(remainder_combination)}
table.insert(combination, num)

(编辑:Lua 5.2+它是table.unpack)