【高级技巧】回溯算法：组合枚举的剪枝策略封装

local best = { value = 0, picks = {} }
local function backtrack(items, idx, curValue, curWeight, cap, picked)
    if curWeight > cap then
        return
    end
    if curValue > best.value then
        best.value = curValue
        best.picks = {}
        for _, p in ipairs(picked) do
            best.picks[#best.picks + 1] = p
        end
    end
    if idx > #items then
        return
    end
    local remain = 0
    for i = idx, #items do
        remain = remain + items[i].value
    end
    if curValue + remain <= best.value then
        return
    end
    picked[#picked + 1] = idx
    backtrack(items, idx + 1, curValue + items[idx].value,
        curWeight + items[idx].weight, cap, picked)
    table.remove(picked)
    backtrack(items, idx + 1, curValue, curWeight, cap, picked)
end

local items = {
    { value = 50, weight = 10 },
    { value = 80, weight = 20 },
}
backtrack(items, 1, 0, 0, 25, {})
print("最优价值 " .. best.value)