贪婪算法(lua实现)

按贪婪算法思路：从树中选择树中值最大的的分支走，依些类推，计算结果为14=4+7+3

function newTree(data)
    local t = {}
    t.data = data
    t.treeList = {}
    return t
end

function addTree(root, tree)
    local treeList = root.treeList
    treeList[#treeList+1] = tree
end

function getMaxGreedy(tree)
    local num = tree.data
    local treeList = tree.treeList

    local function sort(tree1, tree2)
        return tree1.data > tree2.data
    end

    table.sort(treeList, sort)

    if #treeList > 0 then
        local v = 0
        if #treeList > 0 then
            v = getMaxGreedy(treeList[1])
        else
            v = t.data
        end
        num = num + v
    end
    return num
end

local t1  = newTree(1)
local t2  = newTree(2)
local t3  = newTree(3)
local t4  = newTree(4)
local t5  = newTree(5)
local t6  = newTree(6)
local t7  = newTree(7)
local t8  = newTree(8)
local t9  = newTree(9)
local t10 = newTree(10)

local root = newTree(4)

addTree(t4, t9)
addTree(t4, t6)
addTree(t2, t10)
addTree(t2, t1)
addTree(t5, t4)
addTree(t5, t8)
addTree(t7, t3)
addTree(t7, t2)
addTree(root, t5)
addTree(root, t7)

print(getMaxGreedy(root))