动态最优解

function __Class:myTest(num)

    local cost = {5,21,10,8}

    self:botton_up_cut(cost,91)

end

function __Class:botton_up_cut(p,n )

    local count = 0

    local r={}

    table.sort(p,function ( a,b )

        return a>b

    end)

    dump(p)

    local item = {}

    for j=0,n do

        item[j]={}

        for i,v in ipairs(p) do

            item[j][v] = 0

        end

    end

    r[0] = 0;

    local q;

    for j=1,n do

        q= r[j-1]>0 and r[j-1] or 9999999

        item[j] = r[j-1]>0 and clone(item[j-1]) or item[j]

        local tmpw =0

        for k,w in ipairs(p) do

            for i=1,j do

                local t1 = q-j

                local t2 = w+r[j-i]-j

                count = count+1

                if t1 <0 and t2 >=0 then

                    q = w+r[j-i]

                    item[j] = clone(item[j-i])

                    item[j][w]= item[j][w]+1

                    if q-j <=0 then

                        break

                    end

                end

                if t1>=0 and t2 >=0 then

                    q = t1<=t2 and q or w+r[j-i]

                    if t1>t2 then

                        item[j] = clone(item[j-i])

                        item[j][w]= item[j][w]+1

                    end

                    if q-j <=0 then

                        break

                    end

                end

            end

            if q-j <=0 then

                break

            end

        end

        r[j] = q;

        print("n==="..j.."  r====="..r[j].."      circle count:"..count)

        dump(item[j])

    end

    -- print("n==="..n.."  r====="..r[n].."      circle count:"..count)

    --  dump(item[n])

    return q

end