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

local best
local function backtrack(i, weight, score, pick, items, cap)
    if score > (best and best.score or -1) then
        best = { score = score, pick = { unpack(pick) } }
    end
    if i > #items then
        return
    end
    if weight + items[i].w <= cap then
        pick[#pick + 1] = i
        backtrack(i + 1, weight + items[i].w,
            score + items[i].v, pick, items, cap)
        table.remove(pick)
    end
    backtrack(i + 1, weight, score, pick, items, cap)
end

local items = {
    { w = 5, v = 80 }, { w = 3, v = 60 },
    { w = 7, v = 100 }, { w = 2, v = 40 }
}
backtrack(1, 0, 0, {}, items, 10)
print(best.score)