动态规划Lua实现

—参考 http://blog.csdn.net/u013445530/article/details/45645307

最少硬币

--d(i)=min{ d(i - vj )+ 1 }
dp = {}
local min = 11
for i = 0,min do
    dp[i] = i
end 
a = {1,3,5}
for i = 1,min do
    for j = 1,3 do
        if i >= a[j] and  dp[i - a[j]] + 1 < dp[i] then
            dp[i] = dp[i- a[j] ] + 1
        end
    end
end 
for i = 1,min do
    --print(dp[i])
end

倒三角

--f[i][j] = max(f[i+1][j], f[i+1][j+1]) + map[i][j]
map = {
{7},
{3,8},
{8,1,0},
{2,7,4,4},
{4,5,2,6,5},
}

f = {
{7},
{3,8},
{8,1,0},
{2,7,4,4},
{4,5,2,6,5},
}

--自底向上
for i = #map - 1,1,-1 do
    for j =  1,i do
        f[i][j] = math.max(f[i+1][j],f[i+1][j+1]) + map[i][j]
    end
end

print(f[1][1])

01背包

--用一个数组f[i][j]表示，在只有i个物品，容量为j
--f[i+1][j] = max(f[i][j],f[i][j-weight[i+1]+value[i+1])
nameArr = {'a','b','c','d','e'};  
weightArr = {2,2,6,5,4};  
valueArr = {6,3,5,4,6};  
total = 10
--初始化主要初始容量为0和物品为0时的情况
f = {}
for i = 0 ,# nameArr do    
    f[i] = {}
    for j = 0 ,total do
        f[i][j] = 0
    end
end 

for i = 1,# nameArr do    
    for j = 1 ,total do
        if weightArr[i] > j then
        --装不下
            f[i][j] = f[i-1][j]
        else
        --装下时
            f[i][j] =  math.max( f[i-1][j - weightArr[i]] + valueArr[i],f[i-1][j])
        end 
    end
end