编写寻找若干个数字使它们加起来等于某一特定数值的函数

没有解决方案适用于1、2和大于5的值，因此该函数只接受3、4和5。

这里我们进行了times表的浅复制，然后从副本中获取一个随机索引并开始搜索解决方案，在进行过程中，我们会移除已使用的值。

local times = {
    0.5,
    1.0,
    1.5,
    2.0,
    2.5,
    3.0,
    3.5,
    4.0
}

function nNumbersTo8(amount)

    if amount < 3 or amount > 5 then
      return {}
    end

    local sum = 0
    local numbers = {}

    local set = {table.unpack(times)}

    for i = 1, amount - 1, 1 do
        local index = math.random(#set)
        local value = set[index]

        if not (8 < (sum + value)) then
            sum = sum + value
            table.insert(numbers, value)
            table.remove(set, index)
        else
            break
        end
    end
    local reminder = 8 - sum

    for _,v in ipairs(set)do
        if v == reminder then
            sum = sum + v
            table.insert(numbers, v)
            break
        end
    end

    if #numbers == amount then
        return numbers
    else
        return nNumbersTo8(amount)
    end
end

for i=1,100 do
  print(table.unpack(nNumbersTo8(5)))
end

示例响应：

1.5 0.5 3   2   1
3   0.5 1.5 1   2
2   3   1.5 0.5 1
3   2   1.5 1   0.5
0.5 1   2   3   1.5

这是具有选择元素数量的额外限制的子集和问题。解决方案是使用类似于常规子集和的动态规划，但添加一个额外的变量表示已使用的项目数。

应该按以下方式进行：

失败的停止子句：
DP [ -1 ] [ x ] [n] = false，对于所有 x，n > 0 //超出元素
DP [i] [-1] [n] = false，对于所有 i，n > 0 //超过 X 项
DP [i] [x] [n] = false n <0 //通过总和限制。如果所有元素均为非负数，则这是一种优化。
成功的停止子句：
DP [i] [0] [0] = true，对于所有 i> = 0

递归公式：
DP [i] [x] [n] = DP [i-1] [x] [n] OR DP [i-1] [x-1] [n- item [ i ]] //注意n <item [i]情况。
              ^ ^
未使用项目已使用项目

下面是一种适用于大量元素的方法，并将每个解决方案以理论上相同的可能性随机选取。

function solution_node (value, count, remainder)
    local node = {}
    node.value = value
    node.count = count
    node.remainder = remainder
    return node
end

function choose_solutions (node1, node2)
    if node1 == nil then
        return node2
    elseif node2 == nil then
        return node1
    else
        -- 以随机方式选择哪个解决方案。
        if node1.count < math.random(node1.count + node2.count) then
            node2.count = node1.count + node2.count
            return node2
        else
            node1.count = node1.count + node2.count
            return node1
        end
    end
end

function decode_solution (node)
    if node == nil then
        return nil
    end

    answer = {}
    while node.value ~= nil do
        table.insert(answer, node.value)
        -- 这使得解决方案被随机洗牌。
        local i = math.random(#answer)
        answer[#answer], answer[i] = answer[i], answer[#answer]
        node = node.remainder
    end
    return answer
end

function random_sum(tbl, count, target)
    local choices = {}
    -- 在 Lua 中，通常数组不是从 0 开始的，但这很方便。
    for j = 0,count do
        choices[j] = {}
    end
    -- 确保空集存在。
    choices[0][0.0] = solution_node(nil, 1,  nil)

    for i = 1,#tbl do
        for j = count,1,-1 do
            for this_sum, node in pairs(choices[j-1]) do
                local next_sum = this_sum + tbl[i]
                local next_node = solution_node(tbl[i], node.count, node)
                -- 尝试将此值添加到一个解决方案中。
                if next_sum <= target then
                    choices[j][next_sum] = choose_solutions(next_node, choices[j][next_sum])
                end
            end
        end
    end

    return decode_solution(choices[count][target])
end

local times = {
    0.2,
    0.3,
    0.5,
    1.0,
    1.2,
    1.3,
    1.5,
    2.0,
    2.5,
    3.0,
    3.5,
    4.0
}

math.randomseed( os.time() )
local result = random_sum(times, 5, 8.0)
print("answer")
for k, v in pairs(result) do print(v) end